问题：
给定一棵二叉树，对所有节点为root的子树，若存在重复的子树。将该节点加入res。
Example 1: Input: root = [1,2,3,4,null,2,4,null,null,4] Output: [[2,4],[4]] Example 2: Input: root = [2,1,1] Output: [[1]] Example 3: Input: root = [2,2,2,3,null,3,null] Output: [[2,3],[3]] Constraints: The number of the nodes in the tree will be in the range [1, 10^4] -200 <= Node.val <= 200
解法：
对每个节点：我们应该做什么？
1. 看看以该节点为root的子树，是什么样子的？-> 递归
2. 将1.中得到的子树，在所有遍历过的子树all_subtrees中，进行对比。
3. 如果已经存在同样的子树：将该节点加入res
4. 如果不存在这样的子树：将该节点加入遍历过的子树all_subtrees群中
?? 注意：
在第3步中，可能在res中，存入重复的子树，
因此，在 遍历过的子树all_subtrees中，记录比对次数，当只比对过一次的时候，才加入res。
代码参考：
1 /** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode() : val(0), left(nullptr), right(nullptr) {} 8 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} 9 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} 10 * }; 11 */ 12 class Solution { 13 public: 14 unordered_map<string, int> all_subtrees; 15 vector<TreeNode*> res; 16 //for each node: 17 //1. find one‘s tree -> get the tree all node 18 //2. use 1. to compare all_subtrees of the root. 19 //3. if there is a same tree in 2. , then res.append(this.node) 20 //4. else all_subtrees.append(this.node) 21 vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) { 22 traverse(root); 23 return res; 24 } 25 string traverse(TreeNode* root) { 26 if(!root) return string("#"); 27 //1. find one‘s tree -> get the tree all node 28 string left = traverse(root->left); 29 string right = traverse(root->right); 30 string mytree = left+","+right+","+to_string(root->val); 31 //2. use 1. to compare all_subtrees of the root. 32 if(all_subtrees.count(mytree)!=0) { 33 //3. if there is a same tree in 2. , then res.append(this.node) 34 if(all_subtrees[mytree]==1) res.push_back(root); 35 all_subtrees[mytree]++; 36 } else { 37 //4. else all_subtrees.append(this.node) 38 //all_subtrees[mytree]++; 39 all_subtrees[mytree]=1; 40 } 41 return mytree; 42 } 43 };
【二叉树思想】652. Find Duplicate Subtrees
原文：https://www.cnblogs.com/habibah-chang/p/13835844.html