Leetcode Link: 剑指 Offer 26. 树的子结构 - 力扣（LeetCode） (leetcode-cn.com)
题目
输入两棵二叉树 A 和 B，判断 B 是不是 A 的子结构。(约定空树不是任意一个树的子结构)
B 是 A 的子结构，即 A 中有出现和 B 相同的结构和节点值。
求两者先序、后序的后查找存不存在的思路可能的问题
开始想的是先把两个输入的先序或者后序的结果找出来，然后在A的结果里看B的顺序存在不存在。这种思路可能有问题，因为如果B是单边树（每层只含有一个孩子，方向不一定），如果B的深度大一些，其先序后序的顺序就和A不一样了，但是也有可能是A的子结构。
解法一
思路：遍历加检查，简单粗暴，类似指针游走。
题解：
class Solution:
def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
if not B:
return False
self.B = B
self.res = []
self.traverse(A)
return sum(self.res)>0
def traverse(self, root):
if not root:
return None
# 如果当前 A 的节点和 B 的头节点相等，就开始检查
# 这里有点冗余了，因为每次 B 都要走一遍
# 不知道能不能改进
if root.val == self.B.val:
self.res.append(self.check(root))
self.traverse(root.left)
self.traverse(root.right)
def check(self, root):
q1 = collections.deque()
qb = collections.deque()
q1.append(root)
qb.append(self.B)
while(qb):
cur1 = q1.popleft()
curb = qb.popleft()
if cur1.val != curb.val:
return False
if curb.left:
# 如果 B 还存在孩子而 1 已经没孩子了
# 肯定不是子结构，反过来不一定
if not cur1.left:
return False
q1.append(cur1.left)
qb.append(curb.left)
if curb.right:
if not cur1.right:
return False
q1.append(cur1.right)
qb.append(curb.right)
return True
解法二
思路：思路也是一样的，不过从迭代变成了两个递归，代码理解上可能更复杂一些。 面试题26. 树的子结构（先序遍历 + 包含判断，清晰图解） - 树的子结构 - 力扣（LeetCode） (leetcode-cn.com)
题解：
class Solution:
def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
def recur(A, B):
"""B为A子树，且AB根节点相同"""
# B 被遍历空，返回True
if not B:
return True
# 防止 A.val 报错
if not A:
return False
# 值不同，返回False
if A.val != B.val:
return False
# 继续递归遍历后续子树是否相同
return recur(A.left, B.left) and recur(A.right, B.right)
# A或B为空时，按照题目要求，返回False
if not A or not B:
return False
# 通过递归将A的结点分别和B进行比较
return recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)
复习时自己写的代码，更好理解
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
if not B:
return False
def bfsA(node): # 遍历A，找到可能的位置再检查A和B
if not node:
return False
if node.val == B.val:
if check(node, B):
return True
return bfsA(node.left) or bfsA(node.right)
def check(a,b):
# 这里不能是 if not a and not b, 必需只判断b
# 因为a是可以继续走下去的！
if not b:
return True
if type(a) != type(b):
return False
if a.val != b.val:
return False
return check(a.left, b.left) and check(a.right, b.right)
return bfsA(A)