572. 另一个树的子树

题目来源：https://leetcode-cn.com/problems/subtree-of-another-tree

题目

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

示例 1:

给定的树 s:

     3
    / \
   4   5
  / \
 1   2

给定的树 t：

   4 
  / \
 1   2

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

示例 2:

给定的树 s：

     3
    / \
   4   5
  / \
 1   2
    /
   0

给定的树 t：

   4
  / \
 1   2

返回 false。

解题思路

思路：深度优先搜索

在这里，先分析题意：

• 一个二叉树若为另一个树的子树，则它含有与另外一个树的子树相同结构和节点值。
• 根据示例 2 可知，判断是否为子树，必须有完全相同结构和节点值。

以下 s、t 表示两个二叉树，题目要求判断 t 是否是 s 的子树

现在将题意转换为可实现代码书写的思路，判断两个树是否相等，那么下面的条件必须同时成立：

• 当前两个树根节点值相同；
• s 的左子树与 t 的左子树相同；
• s 的右子树与 t 的右子树相同。

根据上面的思路，本篇幅考虑使用深度优化搜索的方法，枚举 s 的每个节点，判断这个点的子树是否与 t 相等。使用深度优先搜索检查，从根出发，同步移动遍历两个树，判断相应的位置是否相等。

具体的代码实现如下。

代码实现

# 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:
        return self.dfs(s, t)
    
    def dfs(self, c, t):
        # c 子树为空时，返回 False
        if not c:
            return False
        return self.is_same(c, t) or self.dfs(c.left, t) or self.dfs(c.right, t)
    
    def is_same(self, c, t):
        # 两个树都为空时，也认为是相同
        if (not c) and (not t):
            return True
        # 当其中一个树为空，但另外一个树不为空时，此时则为不同
        if (not c and t) or (c and not t):
            return False
        # 两个树都不为空，若值不同，也为不同
        if (c.val != t.val):
            return False
        # 上面的情况都不符合时，继续向下检查
        return self.is_same(c.left, t.left) and self.is_same(c.right, t.right)
        

实现结果

以上就是使用深度优先搜索，枚举 s 的每个节点与 t 进行匹配，进而解决《572. 另一个树的子树》问题的主要内容。

欢迎关注微信公众号《书所集录》