题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
思路
首先找到root1结点值和root2结点值相等的点,遍历比对这两个结点的子树是否完全一致.
需要注意的几个点
1.这里可能存在重复值的情况存在,因此如果遍历一个结点其子树和比对子树不一致,我们仍然需要向下遍历.如图所示我们比对第一个8,如果比对不成功,我们仍然需要继续比对子树
2.我们在比对子树时候,如果我们比对当前结点值和目标结点值一致,我们仍然需要比对它的左右子树,这里我们必须保证,左右子树必须都要和目标结点的左右子树相同才行,因此第二个子树判断函数最后一行代码里用的是&&而不是||
代码:
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
boolean sign=false;
if (root2==null||root1==null){
return false;
}
if (root1.val==root2.val){
sign=judgeChild(root1,root2);
}
if (!sign){
return HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2);
}
return sign;
}
private boolean judgeChild(TreeNode root1, TreeNode root2) {
if (root1==null&&root2!=null){
return false;
}
if (root2==null){
return true;
}
if (root1.val!=root2.val){
return false;
}
return judgeChild(root1.left,root2.left)&&judgeChild(root1.right,root2.right);
}
