JZ26 树的子结构 ☆☆☆
描述
输入两棵二叉树A,B,判断B是不是A的子结构。(我们约定空树不是任意一个树的子结构)
假如给定A为{8,8,7,9,2,#,#,#,#,4,7},B为{8,9,2},2个树的结构如下,可以看出B是A的子结构
数据范围:
0 <= A的节点个数 <= 10000
0 <= B的节点个数 <= 10000
示例1
输入:{8,8,7,9,2,#,#,#,#,4,7},{8,9,2}
返回值:true
示例2
输入:{1,2,3,4,5},{2,4}
返回值:true
示例3
输入:{1,2,3},{3,1}
返回值:false
思路:
hasSubtree(A,B):isSubtree(A,B)or A的左子树 or A的右子树
isSubtree(A,B):根值相同,A左子树包含B左子树,A右子树包含A右子树
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def HasSubtree(self , pRoot1: TreeNode, pRoot2: TreeNode) -> bool:
if not pRoot1 or not pRoot2: return False
return self.isSub(pRoot1, pRoot2) or self.HasSubtree(pRoot1.left, pRoot2) or self.HasSubtree(pRoot1.right, pRoot2)
def isSub(self, p1, p2):
if not p2: return True
if not p1: return False
return p1.val==p2.val and self.isSub(p1.left, p2.left) and self.isSub(p1.right, p2.right)