递归方法判断子树
- 要判断B树是不是A的子树,就肯定要遍历A树的每一个节点
- 然后把A树的每一个节点当作根节点与B树进行比较-->进入子树判断方法
- 子树判断的三种情况:(当前节点)
- B树为空,说明B树遍历完毕,A树包含B树所有节点 -->true
- A树为空 (B树不为空),说明B树有节点而A树对应位置节点为空 -->false
- A,B树都不为空,判断val,
//对于A树来说,只要有一个节点满足子树判断即为true
return HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2);
//对于子树判断方法来说,只有所有节点都相等才为true
return isOk(node1.left,node2.left)&&isOk(node1.right,node2.right);
===================上面都是废话===================
public class Solution {
/*
判断B树是不是A树的子树
1.遍历A树节点,若当前节点与B树root节点相等:
同时进入左节点判断:不相等->返回继续遍历
相等->进入下一个节点判断
2.若B树遍历完了,则说明存在该子树
若A树遍历完了,则说明不存在该子树
*/
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if(root1==null||root2==null){ //root2为空B为空树,root1为空A树遍历完毕
return false;
}
// 直接比较每一个节点的方式
if(isOk(root1,root2)){ //判断当前A树节点与B树的关系
return true;
}else{
//递归遍历左右子树,只要有一个节点满足即可
return HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2);
}
}
public boolean isOk(TreeNode node1,TreeNode node2){
if(node2==null){ //B树遍历完毕,说明B树是A树的子树
return true;
}else if(node1==null ){ //B树未遍历完,但A树遍历完了,说明B树不是A的子树
return false;
}
//A,B树都还没遍历完
if(node1.val!=node2.val){ //A,B树当前节点值不相等,返回false
return false;
}
//A,B树当前节点相等,进入下一节点比较
//只有所有节点都相等才为true
return isOk(node1.left,node2.left)&&isOk(node1.right,node2.right);
}
}