一、题目描述
输入两棵二叉树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
二、思路讲解
判断B是否是A的子结构，毫无疑问是要遍历A的，关键在于如何分解子问题，再递归求解。
我们可以用函数isSubStructure（A，B）来先序遍历A，用函数fun（A,B）来判断A中是否含有B。
那么，我们就先序遍历A，然后判断B是否在A中。
看一下fun函数的终止条件：
1、B == null 说明B已经穿过叶子节点，没有出现问题，说明B是A的子结构，返回true；
2、A == null 说明A已经穿过了叶子节点，还是没有找到能够返回true的条件（和B相同的结构），说明应该返回false；
3、A.val != B.val 说明A的根节点与B的根节点值不相同，返回false
没有出现以上三种情况，说明遍历到目前为止，A的结构中目前可能存在B相同的结构，至于是否真的存在B这样的结构，还需要看看A的左子树和B的左子树、A的右子树和B的右子树是否有相同结构，fun(A.left, B.left)，fun(A.right, B.right)
再看一下isSubStructure的终止条件：
1、A==null || B==null 说明一直找到A或者B的根节点都没有找到相同结构，返回false
或者说明A或B本身就是空树，返回false
2、A中有B的结构，或者A的左子树中有B的结构，或者A的右子树中有B的结构（先序遍历A），只要满足一个就返回true，否则返回false。
三、Java代码实现
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isSubStructure(TreeNode A, TreeNode B) { //已经穿过叶子节点，说明整棵树中没有符合的结构 //或者本身就是空树 if(A==null || B==null){ return false; } //如果B是A的子结构 或者B是A的左子树的子结构 或者B是A的右子树的子结构 //三个条件满足其中一个则返回true，都不满足则返回false（也就是先序遍历A） return fun(A, B)||isSubStructure(A.left, B)||isSubStructure(A.right, B); } //判断B是否是A的子结构 public static boolean fun(TreeNode A, TreeNode B){ //如果B为空，说明此时已经穿过了B的叶子节点，B是A的子结构 if(B == null){ return true; } //如果A为空，说明此时已经传过了A的叶子节点，说明A中没有与B相同的结构 //如果A的值与B不相等，说明不符合条件 if(A == null || A.val!=B.val){ return false; } //能够到达这一步说明A和B的值相同，那就再比较左右子树是否相同 return fun(A.left, B.left) && fun(A.right, B.right); } }
四、时空复杂度分析
看一下力扣大佬的复杂度分析：
