0652：寻找重复的子树（★）

2016-10-13 约 305 字预计阅读 1 分钟次阅读

力扣第 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]]

提示：

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

分析

需要判断任意两个子树是否相同，可以将每个子树都序列化，方便比较。

更进一步，用哈希表保存序列化值出现的次数，一趟遍历即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
    def serial(root):
        key = '#' if not root else '%d,%s,%s' % (root.val, serial(root.left), serial(root.right))
        d[key] += 1
        if key != '#' and d[key] == 2:
            res.append(root)
        return key

    res, d = [], defaultdict(int)
    serial(root)
    return res

80 ms

目录

0652：寻找重复的子树（★）

题目

分析

解答