Leetcode-572 另一个树的子树

发表于 更新于

给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

示例 1:
给定的树 s:

1
2
3
4
5
6
    3
   / \
  4   5
 / \
1   2

给定的树 t：

1
2
3
  4 
 / \
1   2

返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。

示例 2:
给定的树 s：

1
2
3
4
5
6
7
    3
   / \
  4   5
 / \
1   2
   /
  0

给定的树 t：

1
2
3
  4
 / \
1   2

返回 false。

思路

这题是让我们判断一个树是否是另外一个树的子树，从题目的一开始s 的一个子树包括 s 的一个节点和这个节点的所有子孙结合第二个例子不难发现，中间的某个部分不能算是子树。那么就相当于需要判断s的所有子树中是否和t有一样的，最后就演变成判断两个树是否相等了。判断俩个树是否相等，可以用递归的写法。

判断两个树是否相等

1
2
3
4
5
6
7
8
def isSameTree(s: TreeNode, t: TreeNode) -> bool:
    if not s and not t:
        return True
    if not s or not t:
        return False
    if s.val != t.val:
        return False
    return isSameTree(s.left,t.left) and isSameTree(s.right,t.right)

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        def isSameTree(s: TreeNode, t: TreeNode) -> bool:
            if not s and not t:
                return True
            if not s or not t:
                return False
            if s.val != t.val:
                return False
            return isSameTree(s.left,t.left) and isSameTree(s.right,t.right)
        if not s:
            return False
        if isSameTree(s,t):
            return True
        return self.isSubtree(s.left,t) or self.isSubtree(s.right,t)

开放思路

如果我们把两个树的所有节点值都保存到两个字符串 s’ 和 t’ 中，然后判断是否 t’ 在 s’ 中就能得出 t 是否是 s 的子树了？

答案是肯定的，有兴趣的可以按照这个思路去实践一下。