后序遍历，递归和迭代 2 种算法，用哈希映射数据结构，字符串或元组构造键名，用序列化技巧，求解《652. 寻找重复的子树》

var findDuplicateSubtrees = function(root) {
  let i = 0
  const h = new Map, ans = [], d = n => {
    if (n == null) return 0
    const s = n.val + ',' + d(n.left) + ',' + d(n.right)
    if (h.has(s) === false) h.set(s, [++i, 0])
    else if (h.get(s)[1] === 0) {
      ans.push(n)
      h.get(s)[1] = 1
    }
    return h.get(s)[0]
  }
  return d(root), ans
};

function findDuplicateSubtrees(root: TreeNode | null): Array<TreeNode | null> {
  const h = new Map, ans = []
  let i = 0
  const d = n => {
    if (n === null) return 0
    const s = n.val + ',' + d(n.left) + ',' + d(n.right)
    if (h.has(s)) {
      if (h.get(s)[1] === 0) {
        ans.push(n)
        h.get(s)[1] = 1
      }
    } else {
      h.set(s, [++i, 0])
    }
    return h.get(s)[0]
  }
  return d(root), ans
};

class Solution {
  private $h = array();
  private $i = 0;
  private $ans = array();
  function d($n) {
    if ($n === null) return 0;
    $s = $n->val . ',' . $this->d($n->left) . ',' . $this->d($n->right);
    if ($this->h[$s] === null) {
      $this->h[$s] = array(++$this->i, 0);
    } else {
      if ($this->h[$s][1] === 0) {
        $this->ans []= $n;
        $this->h[$s][1] = 1;
      }
    }
    return $this->h[$s][0];
  }
  function findDuplicateSubtrees($root) {
    $this->d($root);
    return $this->ans;
  }
}

func findDuplicateSubtrees(root *TreeNode) []*TreeNode {
  i, h, ans := 0, map[[3]int][2]int{}, []*TreeNode{} 
  var d func(n *TreeNode) int
  d = func(n *TreeNode) int {
    if n == nil {
      return 0
    }
    s := [3]int{n.Val, d(n.Left), d(n.Right)}
    if _, ok := h[s]; ok == false {
      i++
      h[s] = [2]int{i, 0}
    } else if (h[s][1] == 0) {
      ans = append(ans, n)
      h[s] = [2]int{h[s][0], 1}
    }
    return h[s][0]
  }
  d(root)
  return ans
}

class Solution {
  private int i = 0;
  private Map<String, int[]> h = new HashMap<String, int[]>();
  private List<TreeNode> ans = new ArrayList<TreeNode>();
  private int d(TreeNode n) {
    if (n == null) return 0;
    String s = n.val + "," + d(n.left) + "," + d(n.right);
    if (h.containsKey(s) == false) {
      i++;
      h.put(s, new int[]{i, 0});
    } else if (h.get(s)[1] == 0) {
      ans.add(n);
      h.get(s)[1] = 1;
    }
    return h.get(s)[0];
  }
  public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
    d(root);
    return ans;
  }
}

public class Solution {
  private Dictionary<string, int[]> h = new Dictionary<string, int[]>();
  private int i = 0;
  private List<TreeNode> ans = new List<TreeNode>();
  public int d(TreeNode n) {
    if (n == null) return 0;
    string s = n.val + "," + d(n.left) + "," + d(n.right);
    if (h.ContainsKey(s) == false) {
      h.Add(s, new int[2]{++i, 0});
    } else if (h[s][1] == 0) {
      h[s][1] = 1;
      ans.Add(n);
    }
    return h[s][0];
  }
  public IList<TreeNode> FindDuplicateSubtrees(TreeNode root) {
    d(root);
    return ans;
  }
}

typedef struct {
  char* key;
  int val;
  int i;
  UT_hash_handle hh;
} HashItem;
int d(struct TreeNode* n, HashItem** h, int* i, struct TreeNode** ans, int* pos) {
  if (n == NULL) return 0;
  char* s = malloc(sizeof(char) * 32);
  sprintf(s, "%d,%d,%d", n->val, d(n->left, h, i, ans, pos), d(n->right, h, i, ans, pos));
  HashItem* pEntry = NULL;
  HASH_FIND_STR(*h, s, pEntry);
  if (pEntry == NULL) {
    pEntry = malloc(sizeof(HashItem));
    pEntry->key = s;
    pEntry->val = 0;
    pEntry->i = ++*i;
    HASH_ADD_STR(*h, key, pEntry);
  } else if (pEntry->val == 0) {
    pEntry->val = 1;
    ans[(*pos)++] = n;
  }
  return pEntry->i;
}
struct TreeNode** findDuplicateSubtrees(struct TreeNode* root, int* returnSize){
  HashItem* h = NULL;
  int i = 0, pos = 0;
  struct TreeNode** ans = malloc(sizeof(struct TreeNode*) * 1e4);
  d(root, &h, &i, ans, &pos);
  *returnSize = pos;
  free(h);
  return ans;
}

class Solution {
private:
  unordered_map<string, pair<int, int>> h;
  vector<TreeNode*> ans;
  int i = 0;
  string d(TreeNode* n) {
    if (n == nullptr) return "0";
    string s = to_string(n->val) + "," + d(n->left) + "," + d(n->right);
    if (h.find(s) == h.end()) h.emplace(s, pair{++i, 0});
    else if (h[s].second == 0) {
     h[s].second = 1;
     ans.emplace_back(n);
    }
    return to_string(h[s].first);
  }
public:
  vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
    return d(root), ans;
  }
};

class Solution:
  def d(self, n: Optional[TreeNode]) -> str: # 字符串实现
    if n == None: return '0'
    s = str(n.val) + ',' + self.d(n.left) + ',' + self.d(n.right)
    if s not in self.h: 
      self.i += 1
      self.h[s] = [self.i, 0]
    elif self.h[s][1] == 0:
      self.h[s][1] = 1
      self.ans.append(n)
    return str(self.h[s][0])
  def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
    self.h, self.i, self.ans = dict(), 0, []
    self.d(root)
    return self.ans

class Solution:
  def d(self, n: Optional[TreeNode]) -> int:  # 元组实现
    if n == None: return 0
    s = (n.val, self.d(n.left), self.d(n.right))
    if s not in self.h: 
      self.i += 1
      self.h[s] = [self.i, 0]
    elif self.h[s][1] == 0:
      self.h[s][1] = 1
      self.ans.append(n)
    return self.h[s][0]
  def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
    self.h, self.i, self.ans = dict(), 0, []
    self.d(root)
    return self.ans

var findDuplicateSubtrees = function(root) {
  const stack = [], is = new Map, h = new Map, ans = []
  let p = root, prev = null, i = 0
  while (stack.length || p) {
    while (p) {
      stack.push(p)
      p = p.left
    }
    const n = stack.pop()
    if (n.right === null || n.right === prev) {
      const s = n.val + ',' + is.get(n.left) + ',' + is.get(n.right)
      if (h.has(s) === false) {
        h.set(s, [i++, 0])
      } else if (h.get(s)[1] === 0) {
        ans.push(n)
        h.get(s)[1] = 1
      }
      is.set(n, h.get(s)[0])
      prev = n
    } else {
      stack.push(n)
      p = n.right
    }
  }
  return ans
};

function findDuplicateSubtrees(root: TreeNode | null): Array<TreeNode | null> {
  const stack = [], ans = [], is = new Map, h = new Map
  let p = root, prev = null, i = 0
  while (stack.length || p) {
    while (p) {
      stack.push(p)
      p = p.left
    }
    const n = stack.pop()
    if (n.right === null || n.right === prev) {
      const s = n.val + ',' + is.get(n.left) + ',' + is.get(n.right)
      if (h.has(s) === false) {
        h.set(s, [i++, 0])
      } else if (h.get(s)[1] === 0) {
        ans.push(n)
        h.get(s)[1] = 1
      }
      is.set(n, h.get(s)[0])
      prev = n
    } else {
      stack.push(n)
      p = n.right
    }
  }
  return ans
};

class Solution {
  function findDuplicateSubtrees($root) {
    $stack = array();
    $ans = array();
    $h = array();
    $i = 0;
    $p = $root;
    $prev = null;
    while (count($stack) || $p) {
      while ($p) {
        $stack []= $p;
        $p = $p->left;
      }
      $n = array_pop($stack);
      if ($n->right === null || $n->right === $prev) {
        $s = $n->val . ',' . $n->left->i . ',' . $n->right->i;
        if ($h[$s] === null) {
          $h[$s] = array(++$i, 0);
        } elseif ($h[$s][1] === 0) {
          $h[$s][1] = 1;
          $ans []= $n;
        }
        $n->i = $h[$s][0];
        $prev = $n;
      } else {
        $stack []= $n;
        $p = $n->right;
      }
    }
    return $ans;
  }
}

func findDuplicateSubtrees(root *TreeNode) []*TreeNode {
  var prev *TreeNode
  i, p, stack, ans, is, h := 0, root, []*TreeNode{}, []*TreeNode{}, map[*TreeNode]int{}, map[[3]int][2]int{}
  for len(stack) > 0 || p != nil {
    for p != nil {
      stack = append(stack, p)
      p = p.Left
    }
    n := stack[len(stack) - 1]
    stack = stack[:len(stack) - 1]
    if n.Right == nil || n.Right == prev {
      s := [3]int{n.Val, is[n.Left], is[n.Right]}
      if _, ok := h[s]; ok == false {
        i++
        h[s] = [2]int{i, 0}
      } else if (h[s][1] == 0) {
        ans = append(ans, n)
        h[s] = [2]int{h[s][0], 1}
      }
      is[n] = h[s][0]
      prev = n
    } else {
      stack = append(stack, n)
      p = n.Right
    }
  }
  return ans
}

class Solution {
  public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
    List<TreeNode> ans = new ArrayList<TreeNode>();
    Map<TreeNode, Integer> is = new HashMap<TreeNode, Integer>();
    Map<String, int[]> h = new HashMap<String, int[]>();
    Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
    TreeNode p = root, prev = null;
    int i = 0;
    while (stack.isEmpty() == false || p != null) {
      while (p != null) {
        stack.push(p);
        p = p.left;
      }
      TreeNode n = stack.pop();
      if (n.right == null || n.right == prev) {
        String s = n.val + "," + is.get(n.left) + "," + is.get(n.right);
        if (h.containsKey(s) == false) {
          i++;
          h.put(s, new int[]{i, 0});
        } else if (h.get(s)[1] == 0) {
          ans.add(n);
          h.get(s)[1] = 1;
        }
        is.put(n, h.get(s)[0]);
        prev = n;
      } else {
        stack.push(n);
        p = n.right;
      }
    }
    return ans;
  }
}

public class Solution {
  public IList<TreeNode> FindDuplicateSubtrees(TreeNode root) {
    List<TreeNode> ans = new List<TreeNode>();
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode p = root, prev = null;
    Dictionary<TreeNode, int> d = new Dictionary<TreeNode, int>();
    Dictionary<string, int[]> h = new Dictionary<string, int[]>();
    int i = 0;
    while (stack.Count > 0 || p != null) {
      while (p != null) {
        stack.Push(p);
        p = p.left;
      }
      TreeNode n = stack.Pop();
      if (n.right == null || n.right == prev) {
        string s = n.val + "," + (n.left != null ? d[n.left] : "") + "," + (n.right != null ? d[n.right] : "");
        if (h.ContainsKey(s) == false) {
          h.Add(s, new int[2]{i++, 0});
        } else if (h[s][1] == 0) {
          ans.Add(n);
          h[s][1] = 1;
        }
        d.Add(n, h[s][0]);
        prev = n;
      } else {
        stack.Push(n);
        p = n.right;
      }
    }
    return ans;
  }
}

typedef struct {
  char* key;
  int val;
  int i;
  UT_hash_handle hh;
} HashItem;
typedef struct {
  struct TreeNode* key;
  int i;
  UT_hash_handle hh;
} HashTreeNode;
struct TreeNode** findDuplicateSubtrees(struct TreeNode* root, int* returnSize){
  struct TreeNode** stack = malloc(sizeof(struct TreeNode*) * 1e4);
  int pos = 0, i = 0, j = 0;
  struct TreeNode* p = root;
  struct TreeNode* prev = NULL;
  HashItem* h = NULL;
  HashTreeNode* is = NULL;
  struct TreeNode** ans = malloc(sizeof(struct TreeNode*) * 1e4);
  while (pos || p) {
    while (p) {
      stack[pos++] = p;
      p = p->left;
    }
    struct TreeNode* n = stack[--pos];
    if (n->right == NULL || n->right == prev) {
      HashTreeNode* pNodeEntry = NULL;
      HASH_FIND_INT(is, &n->left, pNodeEntry);
      int l = pNodeEntry ? pNodeEntry->i : 0;
      HASH_FIND_INT(is, &n->right, pNodeEntry);
      char* s = malloc(sizeof(char) * 17);
      sprintf(s, "%d,%d,%d", n->val, l, pNodeEntry ? pNodeEntry->i : 0);
      HashItem* pEntry = NULL;
      HASH_FIND_STR(h, s, pEntry);
      if (pEntry == NULL) {
        pEntry = malloc(sizeof(HashItem));
        pEntry->key = s;
        pEntry->val = 0;
        pEntry->i = ++i;
        HASH_ADD_STR(h, key, pEntry);
      } else if (pEntry->val == 0) {
        pEntry->val = 1;
        ans[j++] = n;
      }
      pNodeEntry = malloc(sizeof(HashTreeNode));
      pNodeEntry->key = n;
      pNodeEntry->i = pEntry->i;
      HASH_ADD_INT(is, key, pNodeEntry);
      prev = n;
    } else {
      stack[pos++] = n;
      p = n->right;
    }
  }
  free(h);
  free(is);
  free(stack);
  free(p);
  free(prev);
  *returnSize = j;
  return ans;
}

class Solution {
public:
  vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
    stack<TreeNode*> st;
    TreeNode* p = root;
    TreeNode* prev = nullptr;
    unordered_map<string, vector<int>> h;
    unordered_map<TreeNode*, string> is;
    int i = 0;
    vector<TreeNode*> ans;
    while (st.empty() == false || p) {
      while (p) {
        st.push(p);
        p = p->left;
      }
      TreeNode* n = st.top();
      st.pop();
      if (n->right == nullptr || n->right == prev) {
        string s = to_string(n->val) + "," + is[n->left] + "," + is[n->right];
        if (h.find(s) == h.end()) h.emplace(s, vector<int>{i++, 0});
        else if (h[s][1] == 0) {
          h[s][1] = 1;
          ans.emplace_back(n);
        }
        is.emplace(n, to_string(h[s][0]));
        prev = n;
      } else {
        st.push(n);
        p = n->right;
      }
    }
    return ans;
  }
};

class Solution:
  def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]: # 字符串实现
    stack, h, d, p, prev, i, ans  = [], {}, {}, root, None, 0, []
    while len(stack) or p:
      while p:
        stack.append(p)
        p = p.left
      n = stack.pop()
      if n.right == None or n.right == prev:
        s = str(n.val) + ',' + (d[n.left] if n.left else '') + ',' + (d[n.right] if n.right else '')
        if s not in h:
          i += 1
          h[s] = [i, 0]
        elif h[s][1] == 0:
          h[s][1] = 1
          ans.append(n)
        d[n] = str(h[s][0])
        prev = n
      else:
        stack.append(n)
        p = n.right
    return ans

class Solution:
  def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]: # 元组实现
    stack, h, d, p, prev, i, ans  = [], {}, {}, root, None, 0, []
    while len(stack) or p:
      while p:
        stack.append(p)
        p = p.left
      n = stack.pop()
      if n.right == None or n.right == prev:
        s = (n.val, d[n.left] if n.left else None, d[n.right] if n.right else None)
        if s not in h:
          i += 1
          h[s] = [i, 0]
        elif h[s][1] == 0:
          h[s][1] = 1
          ans.append(n)
        d[n] = h[s][0]
        prev = n
      else:
        stack.append(n)
        p = n.right
    return ans