树的子结构

问题描述
    
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

解决思路
    首先判断B的根节点和A的根节点是否相同（这里的相同是指节点的值相同并且左右子节点相同），如果相同比较他们的左右子节点，这一步骤是相同的，可以用递归完成，直到B遍历到每个尾节点，如果这一过程比较的所有节点是相同的，则证明B是A的子结构。如果B的根节点和A的根节点不同，则A向他的左右子节点滑动，然后继续跟B的子节点比较，步骤同上。

public class Solution {
  /**
     * 二叉树的构造 内部类
     */
    public class TreeNode{
        int val;
        TreeNode left=null;
        TreeNode right=null;

        public TreeNode(int val) {
            this.val = val;
        }
    }

  
    public static boolean HasSubtree(TreeNode root1,TreeNode root2) {
        boolean result=false;

        //如果root1和root2不为null
        if (root1!=null&&root2!=null){
            //判断两个值是否相同
            if (root1.val==root2.val){
                result=isHaveTree(root1,root2);
            }

            if (!result){
                result=HasSubtree(root1.left,root2);
            }

            if (!result){
                result=HasSubtree(root1.right,root2);
            }

        }
        return result;
    }
    public static boolean isHaveTree(TreeNode root1,TreeNode root2) {
        //如果第二个节点为空 true
        if (root2==null){
            return true;
        }
        //如果第一个节点为空 false
        if (root1==null){
            return false;
        }
        
        //如果不同
        if (root1.val!=root2.val){
            return false;
        }
        //继续递归
        return  isHaveTree(root1.left,root2.left)&&isHaveTree(root1.right,root2.right);
    }
}