LeetCode 652.寻找重复子树

• 题目
• 思路
• 代码(C++)
• 总结

给定一棵二叉树 root，返回所有重复的子树。
对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
如果两棵树具有相同的结构和相同的结点值，则它们是重复的。

示例1
输入：root = [1,2,3,4,null,2,4,null,null,4]
输出：[[2,4],[4]]

示例2
输入：root = [2,1,1]
输出：[[1]]

题目要求找到所有重复子树，所以需要将一棵树的子树以某种方式表示出来并进行比较，如果有相同的就加入结果集。

首先，很明显要遍历一遍树，然后我们要确定遍历顺序，因为遍历时要确定以每个节点为根的子树的形式，所以肯定与其子节点有关，因为需要先知道子节点，才能确定子树。综上，选择后续遍历顺序。

后序遍历时有两个任务：1.确定当前节点的子树形式；2.判断以当前节点为根的子树是不是重复出现的，如果是，加入结果集。

第2点判断是否重复很容易想到用哈希表统计出现次数，如果次数大于1，则表示重复出现，需要加入结果集，并将哈希表中次数加1；如果次数为0，表示目前无重复，将哈希表中次数加1；

另外，如果一个子树出现了3次及以上，则有可能加入结果集2次或更多。而题目要求的结果集中子树不能有重复，所以进一步地，只有第一次重复出现时加入结果集就好。

对整体思路作一总结：后序遍历+哈希表
1.遍历时确定以当前节点为根的子树，并加入哈希表记录次数；
2.通过次数判断是否是重复出现的子树，是则加入结果集，且要注意只加入一次；

class Solution {
public:
    vector res; // 存放重复子树的节点
    unordered_map map; //记录子树的出现次数
    vector findDuplicateSubtrees(TreeNode* root) {
        traverse(root);
        return res;
    }

    string traverse(TreeNode* root) {
        if (root == nullptr) return "#";
        string left = traverse(root->left);
        string right = traverse(root->right);
        string subtree = left + ',' + right + ',' + to_string(root->val);

        int cnt = map[subtree];
        if (cnt == 1) res.push_back(root);
        map[subtree]++;

        return subtree;
    }
};

关于二叉树的题目有两大主要思路：

1. 遍历：思考是否能通过遍历一遍树得到答案？
2. 分解问题（递归）：是否可通过子问题（子树）的答案推导出原问题的答案?

本题属于第一种，通过遍历一遍树，更新结果集。需要注意的是遍历顺序的确定以及遍历时每个节点需要做什么。