题目
输入两棵二叉树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
限制：
0 <= 节点个数 <= 10000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路
递归
首先先序遍历A树，找到B树的根节点
找到B树的根节点以后进一步校验B是否和A的一个子树拥有相同的结构和节点值
主函数：
如果两棵树都为空，返回true
如果其中一颗树为空，返回false
如果当前A树节点为B树根节点，进入校验函数
如果当前A树节点不是B树根# 题目
输入两棵二叉树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
限制：
0 <= 节点个数 <= 10000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路
递归
首先先序遍历A树，找到B树的根节点
找到B树的根节点以后进一步校验B是否和A的一个子树拥有相同的结构和节点值
主函数：
如果两棵树都为空，返回true
如果其中一颗树为空，返回false
如果当前A树节点为B树根节点，进入校验函数
如果当前A树节点不是B树根节点，递归进入A树左子树查找
如果A树左子树也没找到，递归进入A树右子树查找
校验函数：
如果B树节点为空，表示B树已经遍历完，返回true
如果B树不为空，A树已经为空了，返回false
如果两树节点值不同，返回false
如果两树节点值相同，递归继续效验左右子树
时间复杂度 O(MN)： 其中 M,N 分别为树 A 和 树 B 的节点数量
空间复杂度 O(M) ： 当树 A 和树 B 都退化为链表时，递归调用深度最大。节点，递归进入A树左子树查找
如果A树左子树也没找到，递归进入A树右子树查找
校验函数：
如果B树节点为空，表示B树已经遍历完，返回true
如果B树不为空，A树已经为空了，返回false
如果两树节点值不同，返回false
如果两树节点值相同，递归继续效验左右子树
时间复杂度 O(MN)： 其中 M,N 分别为树 A 和 树 B 的节点数量
空间复杂度 O(M) ： 当树 A 和树 B 都退化为链表时，递归调用深度最大。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isSubStructure(A *TreeNode, B *TreeNode) bool {
if A == nil && B == nil{
return true
}
// 空二叉树不属于任何树子树
if A == nil || B == nil{
return false
}
//var ret bool
//if A.Val == B.Val{
// ret = helper(A,B)
//}
//if !ret{
// ret = isSubStructure(A.Left,B)
//}
//if !ret{
// ret = isSubStructure(A.Right,B)
//}
//return ret
// 判断两二叉树根节点是否相等，如果相等则继续递归左右判断是否包含整个子树
// 如果不相等，递归左子树
// 如果A左子树也没有包含B树的，递归右子树
return helper(A,B) || isSubStructure(A.Left,B) || isSubStructure(A.Right,B)
}
func helper(a *TreeNode,b *TreeNode) bool {
// b树为空，说明遍历完了，A中包含子树B
if b == nil{
return true
}
// a树为空，说明A树遍历完了，但B树还有，所以A树不包含子树B
if a == nil{
return false
}
// a树和b树节点不相等
if a.Val != b.Val{
return false
}
// 如果相等，继续递归左右子树判断剩余部分是否符合
return helper(a.Left,b.Left) && helper(a.Right,b.Right)
}