LeetCode Find Duplicate Subtrees Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any one of them. Two trees are duplicate if they have the same structure with same node values. Example 1: 

        1
       / \
      2   3
     /   / \
    4   2   4
       /
      4

The following are two duplicate subtrees:

      2
     /
    4

and

    4

Therefore, you need to return above trees’ root in the form of a list.

---

给定一棵二叉树，要求找出其中的重复子树，每组重复子树输出其中一个子树即可。 去重最好的办法就是hash，所以思想是把每个子树hash到一个unordered_map中，如果有多个子树hash到同一个桶，则出现了重复。 所以问题的关键是怎样对一个子树hash。我们可以把一棵子树表示成 (left_hash, root, right_hash)，其中left_hash和right_hash分别是左子树和右子树的hash字符串，root表示当前根节点的hash字符串。所以这是一个递归定义。规定空节点的hash值为空串””。 根据子树hash的定义，叶子节点的hash值是(“”,val,””)。求解子树hash值的过程可以用中序遍历，左根右。为什么子树hash中需要逗号和括号呢，就是为了保证不同严格区分不同的子树，因为单纯的中序遍历是无法区分某些子树的，比如下面的两个子树，中序遍历结果都是2,1，无法区分；但是用本文的hash方法，得到的hash值分别是(2,1,)和(,2,1)，这两个字符串是有区别的。

  1
 /
2

和

 2
  \
   1

在DFS的过程中，把每个子树的hash值记录到一个unordered_map中，然后遍历unordered_map，如果该桶放了多个子树，则取出其中一个即可。 完整代码如下： [cpp] class Solution { private: string DFS(TreeNode* root, unordered_map<string, vector<TreeNode*>>& inorders) { if (root == NULL)return ""; string left = DFS(root->left, inorders); string right = DFS(root->right, inorders); string cur = "(" + left + "," + to_string(root->val) + "," + right + ")"; inorders[cur].push_back(root); return cur; } public: vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) { unordered_map<string, vector<TreeNode*>> inorders; DFS(root, inorders); vector<TreeNode*> ans; for (auto &it : inorders) { if (it.second.size() > 1) ans.push_back(it.second[0]); } return ans; } }; [/cpp] 本代码提交AC，用时52MS。]]>