# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def dfsEqual(self, root1, root2):
if not root2:
return True
if not root1 or root1.val != root2.val:
return False
return self.dfsEqual(root1.left, root2.left) and self.dfsEqual(root1.right, root2.right)
def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
if not A or not B:
return False
if A.val == B.val:
falg = self.dfsEqual(A, B) # 防止有相同的结点值，如测试用例： A = [3,4,5,1,2], B = [4,1]
if falg:
return True
return self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)
写法二：
这里贴一下大佬的简洁的题解
class Solution:
def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
def recur(A, B):
if not B: return True
if not A or A.val != B.val: return False
return recur(A.left, B.left) and recur(A.right, B.right)
return bool(A and B) and (recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))
