LeetCode 572. 另一个树的子树 | Python（leetcode会员）

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)

实现结果

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。