LeetCode 572. 另一个树的子树 | Python
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. 另一个树的子树》问题的主要内容。
欢迎关注微信公众号《书所集录》
版权声明：本文为yiluolion原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。