题解 | #树的子结构#

递归方法判断子树

• 要判断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);
    }
}