Medium

题目描述

给定一个二叉树的根节点 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]]

提示：

  • 树中的结点数在 [1, 5000] 范围内
  • -200 <= Node.val <= 200

解题思路

这道题的核心思路是序列化 + 哈希表。

要判断两棵子树是否相同，我们需要一种方式来唯一标识每棵子树。最直观的方法是将子树序列化为字符串，相同的子树会产生相同的序列化字符串。

具体步骤：

  1. 使用后序遍历，确保在处理当前节点时，左右子树已经被处理
  2. 对每个节点，将其子树序列化为字符串格式：左子树序列化,右子树序列化,当前节点值
  3. 使用哈希表记录每种序列化字符串出现的次数
  4. 当某个序列化字符串第二次出现时，说明找到了重复子树，将其根节点加入结果

序列化格式选择： 我们采用 左,右,根 的后序遍历格式，空节点用 # 表示。这样可以唯一确定一棵树的结构。

时间复杂度优化： 虽然字符串拼接看起来开销大，但由于树的深度有限，实际表现良好。也可以考虑使用数字ID来优化，但实现更复杂。

代码实现

class Solution {
public:
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        unordered_map<string, int> count;
        vector<TreeNode*> result;
        serialize(root, count, result);
        return result;
    }
    
private:
    string serialize(TreeNode* node, unordered_map<string, int>& count, vector<TreeNode*>& result) {
        if (!node) return "#";
        
        string left = serialize(node->left, count, result);
        string right = serialize(node->right, count, result);
        string curr = left + "," + right + "," + to_string(node->val);
        
        count[curr]++;
        if (count[curr] == 2) {
            result.push_back(node);
        }
        
        return curr;
    }
};

class Solution:
    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        count = {}
        result = []
        
        def serialize(node):
            if not node:
                return "#"
            
            left = serialize(node.left)
            right = serialize(node.right)
            curr = f"{left},{right},{node.val}"
            
            count[curr] = count.get(curr, 0) + 1
            if count[curr] == 2:
                result.append(node)
            
            return curr
        
        serialize(root)
        return result

public class Solution {
    public IList<TreeNode> FindDuplicateSubtrees(TreeNode root) {
        Dictionary<string, int> count = new Dictionary<string, int>();
        List<TreeNode> result = new List<TreeNode>();
        Serialize(root, count, result);
        return result;
    }
    
    private string Serialize(TreeNode node, Dictionary<string, int> count, List<TreeNode> result) {
        if (node == null) return "#";
        
        string left = Serialize(node.left, count, result);
        string right = Serialize(node.right, count, result);
        string curr = $"{left},{right},{node.val}";
        
        count[curr] = count.GetValueOrDefault(curr, 0) + 1;
        if (count[curr] == 2) {
            result.Add(node);
        }
        
        return curr;
    }
}

var findDuplicateSubtrees = function(root) {
    const map = new Map();
    const result = [];
    
    function serialize(node) {
        if (!node) return "null";
        
        const left = serialize(node.left);
        const right = serialize(node.right);
        const subtree = `${node.val},${left},${right}`;
        
        const count = map.get(subtree) || 0;
        if (count === 1) {
            result.push(node);
        }
        map.set(subtree, count + 1);
        
        return subtree;
    }
    
    serialize(root);
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(N²)最坏情况下，每个节点的序列化字符串长度为O(N)，总共N个节点
空间复杂度O(N²)哈希表存储所有序列化字符串，递归栈深度O(N)

相关题目