labuladong手把手带你刷二叉树（第三期）
Q：怎么知道以自己为根节点的二叉树长什么样？
A：可以通过后序遍历（根的左子树+根的右子树+根）得到自己的样子。如果某个子节点处为空，则用
#进行填空Q：怎么知道和别人长得是否一样？
A: 构建一个字典，保存当前节点对应的样子及其出现的次数。再构建一个向量，若字典中键对应的值出现2次，说明有重复，将这个节点加入res中（多次重复也只添加一次到res中）
注意！！！：本题用前序遍历和后序遍历都可以，但用中序遍历时，会有些特殊的case报错。这是因为用 中序遍历 序列化二叉树时，可能出现symmetric structures of this special case
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// 记录所有子树及出现的频次
unordered_map<string, int> memo;
// 记录重复的子树节点
vector<TreeNode *> res;
string traverse(TreeNode * root){
// 递归结束的条件
if (root == nullptr) return "#";
string l=traverse(root->left);
string r=traverse(root->right);
string current=l+","+r+","+to_string(root->val); // 得到自己的样子 （逗号换成空格也可以）
memo[current]+=1; // 把当前的样子存到memo字典中
if (memo[current]==2) res.push_back(root);// 若键对应的值为2，说明有重复，加到res中。若后面有多次重复，则不会继续加到res了
return current;
}
vector<TreeNode *> findDuplicateSubtrees(TreeNode *root) {
traverse(root);
return res;
}
};
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def findDuplicateSubtrees(self, root):
"""
:type root: TreeNode
:rtype: List[TreeNode]
"""
from collections import defaultdict
dic = defaultdict(int)
res = []
def dfs(root):
if not root: return "#"
l = dfs(root.left)
r = dfs(root.right)
# current = l + "," + str(root.val) + "," + r # 错误，除非用特殊的flag标记
# current =l + "," +r + "," + str(root.val) # 正确
current = str(root.val) + "," + l + "," + r # 正确
dic[current] += 1
if dic[current] == 2: res.append(root)
return current
dfs(root)
return res 
