题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
题目分析
在比较树的子结构时，我们可以进行如下考虑：
- 如果B树为A树的子结构，那么，A的某个结构T的根节点与B的根节点相同，并且T的左子树等于B的左子树，T的右子树等于B的右子树
- 其余情况则B不为A的子结构
- 根据以上情况我们可以使用递归的方式，比较A的所有结构的根节点与B的根节点，进行子结构比较即可。
java代码
public static boolean DoesT1IncludeT2(TreeNode root1,TreeNode root2){
if(root2==null){//B树遍历完成，说明B是T的子结构
return true;
}
if(root1==null){//B未完成而T无节点
return false;
}
if(root1.val!=root2.val){// A与T根节点不同
return false;
}
return DoesT1IncludeT2(root1.left,root2.left)&&DoesT1IncludeT2(root1.right,root2.right);//继续进行比较T与B的左右结构
}
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
boolean ans = false;
if(root1==null || root2==null){//空树不为子结构
return false;
}
if(root1.val == root2.val){
ans = DoesT1IncludeT2(root1,root2);//A与B进行比较
}
if (ans!=true){
ans = HasSubtree(root1.left,root2);//A左子树与B进行比较
}
if (ans!=true){
ans = HasSubtree(root1.right,root2);//A右子树与B进行比较
// 有一个为true那么就是真
return ans;
}