0572：另一棵树的子树

2016-07-25 约 384 字预计阅读 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⁴

相似问题：

分析

容易想到递归方法，先比较 root 和 subRoot，不相等就递归到 root 的子树
判断是否相同即是问题 0100 ，可以通过遍历或递归解决
两重递归有些浪费时间了，有个巧妙的想法是将树序列化，就可以直接比较了
更进一步， t 是 s 的子树就等价于 t 的序列化是 s 的序列化的子串

解答

1
2
3
4
5
6
7


class Solution:
    def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:
        def dfs(u):
            if not u:
                return 'None'
            return '(%d,%s,%s)' % (u.val, dfs(u.left), dfs(u.right))
        return dfs(subRoot) in dfs(root)

60 ms

目录

0572：另一棵树的子树

题目

分析

解答