二叉树第三期

如何判断应该用前序、中序还是后序遍历框架。

01 寻找重复的子树

给定一棵二叉树 root，返回所有重复的子树。

对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。

如果两棵树具有相同的结构和相同的结点值，则它们是重复的。

函数签名如下：

vector<TreeNode*> findDuplicateSubtrees(TreeNode* root);

输入是一棵二叉树的根节点 root，返回的是一个列表，里面装着若干个二叉树节点，这些节点对应的子树在原二叉树中是重复存在的。

如下图：

首先，节点 4 本身可以作为一棵子树，且二叉树中有多个节点 4。

类似的，还存在两颗以 2 为根的重复子树。

做题思路：对于某个节点，它应该做什么？

比如，站在图中这个节点 2 上：

如果想知道以自己为根的子树是不是重复的，是否应该被加入结果列表中，需要知道：

• 以我为根的这棵二叉树（子树）长啥样；
• 以其他节点为根的子树都长啥样？

如何知道以自己为根的二叉树长成什么样？

可以判断本题要使用「后序遍历」框架来解决：

因为要知道以自己为根的子树长啥样，需要先知道我的左右子树长啥样，再加上自己，就构成了整棵子树的样子。

我们可以通过拼接字符串的方式把二叉树序列化：

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);
    return subTree;
}

第一个问题就解决了，对于每个节点，递归函数中 subTree 变量就可以描述以该节点为根的二叉树。

现在解决第二个问题，如何知道别人长啥样？借助一个外部数据结构，让每个节点把自己子树的序列化结果存进去，这样，对于每个节点，就可以知道有没有其他节点的子树和自己是否重复。代码如下：

// 记录所有子树以及出现的次数
unordered_map<string, int> memo;
// 记录重复的子树根节点
vector<TreeNode*> 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 freq = memo[subTree];
    if (freq == 1) {
        res.push_back(root);
    }
    // 给子树对应出现的次数 +1
    memo[subTree] += 1;
}
// 主函数
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
    traverse(root);
}