leetcode：652. 寻找重复的子树

题目

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

示例 1：

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

示例 2：

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

示例 3：

输入：root = [2,2,2,3,null,3,null]
输出：[[2,3],[3]]

解答 & 代码

本题需要遍历二叉树的每个节点，对以该节点为根节点的子树进行序列化（序列化结果是要能反序列化回原二叉树的，具有唯一性，不能存在歧义），将序列化结果存在哈希表中来判断是否重复
可以通过后序遍历或前序遍历进行序列化，这里用的后序遍历

/**
 * 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 {
private:
    vector<TreeNode*> result;                    // 结果数组，记录重复子树的根节点
    unordered_map<string, int> subTreeCntMap;    // 哈希表，key = 子树的序列化字符串，val = 出现次数

    // 二叉树的序列化（这里用的后序遍历，前序遍历也行，但中序不行）
    string postOrder(TreeNode* root)
    {
        if(root == nullptr)
            return "n";

        string left = postOrder(root->left);
        string right = postOrder(root->right);
        string cur = left + "," + right + "," + to_string(root->val);
        // cout << root->val << ": " << cur << endl;
        if(subTreeCntMap.count(cur) > 0 && subTreeCntMap[cur] == 1)
            result.push_back(root);
        ++subTreeCntMap[cur];
        return cur;
    }
public:
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        string serial = postOrder(root);
        // cout << serial << endl;
        return result;
    }
};

复杂度分析：设二叉树节点数为 N

• 时间复杂度：后序遍历二叉树，会访问二叉树的每个节点，时间复杂度 O(N)。在每个节点上，会对以该节点为根的子树进行序列化，需要进行字符串拼接，设当前 root->val 的长度为 a，左子树序列的长度为 b，右子树序列的长度为 c，a + b + c —> O(N)。因此，时间复杂度
• 空间复杂度：
  • 递归栈深度取决于二叉树的深度，因此空间复杂度 O(log N)
  • 哈希表 subTreeCntMap 的空间复杂度

执行结果：

执行结果：通过

执行用时：12 ms, 在所有 C++ 提交中击败了 42.60% 的用户
内存消耗：7.3 MB, 在所有 C++ 提交中击败了 25.09% 的用户