题目描述
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
image
示例：
输入：A = [1,2,3], B = [3,1]
输出：false
输入：A = [3,4,5,1,2], B = [4,1]
输出：true
提示：
0 <= 节点个数 <= 10000
题目分析
- 开始，A、B
- 如果A或者B为null，直接返回false
- 检查B是否是A的子结构，如果是，返回true
- B不是A的子结构，检查B是不是A的左子树的结构，以A.left和B回到1
- B既不是A的子结构又不是A的左子树的结构，检查B是不是A的右子树的结构，以A.right和B返回1
- 以上都不符合，返回false
- 检查B是否为A的子结构的算法：
- 开始，A、B
- 如果A为空或者A、B的val不相等，返回false
- 以A.left和B.left回到1，判断A、B左子树是否相等，不等返回false
- 以A.right和B.right回到1，判断A、B右子树是否相等 ，不等返回false
- 如果以上都满足，返回true
public boolean isSubStructure(TreeNode A, TreeNode B) {
if(A == null) return false;
if(B == null) return false;
if(check(A,B))
return true;
if(isSubStructure(A.left,B))
return true;
if(isSubStructure(A.right,B))
return true;
return false;
}
public boolean check(TreeNode a,TreeNode b){
if(a == null && b == null)
return true;
if(a == null) return false;
if(b == null) return true;
if(a.val != b.val)
return false;
return check(a.left,b.left) && check(a.right,b.right);
}
