树的子结构
解题思路 & 方法
遍历 A 树，找到和 B 数相同的 root node
A.left, A.right 和 B ，使用 isSubStructure 递归
当找到相同的 root node 后，再判断这个 root node 下的子树是否相同
使用 subStructureCheck 这个函数
递归情况：A.left、B.left 和 A.right、B.right 进行比较
基情况：
B 被遍历完毕，说明 B 是 A 的子树
A 被遍历完毕 或者 A.val != B.val，说明 B 不是 A 的子树
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def subStructureCheck(self,A :TreeNode, B:TreeNode) -> bool:
if B is None:
return True
if A is None or (A.val != B.val):
return False
return self.subStructureCheck(A.left, B.left) and self.subStructureCheck(A.right, B.right)
def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
result = False
if A and B:
if A.val == B.val:
result = self.subStructureCheck(A,B)
if not result:
result = self.isSubStructure(A.left,B)
if not result:
result = self.isSubStructure(A.right,B)
return result
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/76923.html
