0572：另一棵树的子树

2016-07-25 约 460 字预计阅读 1 分钟次阅读

力扣第 572 题

题目

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例 1：

输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true

示例 2：

输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false

提示：

root 树上的节点数量范围是 [1, 2000]
subRoot 树上的节点数量范围是 [1, 1000]
-10⁴ <= root.val <= 10⁴
-10⁴ <= subRoot.val <= 10⁴

分析

#1

容易想到递归方法，先比较 root 和 subRoot，不相等就递归到 root 的子树。

判断是否相同即是问题 0100，可以通过遍历或递归解决。

两重递归有些浪费时间了，有个巧妙的想法是将树序列化，就可以直接比较了。

用 ‘#’ 表示空节点，那么任意遍历得到的列表都一一对应二叉树。保存每棵子树对应的序列即可。

1
2
3
4
5
6
7
8


def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:
    @lru_cache(None)
    def serial(root):
        return '#' if not root else '%d,%s,%s' % (root.val, serial(root.left), serial(root.right))

    def help(root):
        return bool(root) and (serial(root) == serial(subRoot) or help(root.left) or help(root.right))
    return help(root)

92 ms

#2

还可以更进一步，按类似字典的形式将树序列化，那么 t 是 s 的子树就等价于 t 的序列化是 s 的序列化的子串。

解答

1
2
3
4


def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:
    def serial(root):
        return 'None' if not root else '{val:%d,left:%s,right:%s}' % (root.val,serial(root.left),serial(root.right))
    return serial(subRoot) in serial(root)

80 ms

目录

0572：另一棵树的子树

题目

分析

#1

#2

解答