题目

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

例如:

给定的树 A:

     3
    / \
   4   5
  / \
 1   2
给定的树 B：

   4 
  /
 1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：

输入：A = [1,2,3], B = [3,1]
输出：false

示例 2：

输入：A = [3,4,5,1,2], B = [4,1]
输出：true

题解

如果树B是树A的子树：

• 树A的节点中必须包含树B的根节点
• 树A已此节点为根节点的子树，必须包含树B

以此我们的解题思路即为：

• 前序遍历树A
  • 当节点与树B的根节点相同时，递归检查是否包含树B
  • 当节点与树B的根节点不同时，忽略
• 递归检查是否包含树B
  • 递归检查左子树
  • 递归检查右子树

代码

func isSubStructure(A *TreeNode, B *TreeNode) bool {
	// 特殊场景：
	// 树A为nil时，树B不可能为树A的子树
	// 树B为nil时，空树不是任何一个树的子结构
	if A == nil || B == nil {
		return false
	}
	// 树A和树B根节点相同时，检查树A是否包含树B
	// 不包含时，继续检查子树
	if A.Val == B.Val && checkSub(A, B) {
		return true
	}
	// 检查子树
	return isSubStructure(A.Left, B) || isSubStructure(A.Right, B)
}

// checkSub 递归检查树A是否包含树B
func checkSub(A, B *TreeNode) bool {
	// 树B为nil，递归结束，数A包含树B
	if B == nil {
		return true
	}
	// 树A为nil或树A和树B根节点不同，递归结束，树A不包含树B
	if A == nil || A.Val != B.Val {
		return false
	}
	// 递归检查树A左右子树是否包含树B左右子树
	return checkSub(A.Left, B.Left) && checkSub(A.Right, B.Right)
}