树的子结构

方法一：递归的方式（利用的是深度优先遍历的思想）

    public boolean isSame(TreeNode root1,TreeNode root2){
        //如果root2为空，则为true（不需要考虑root1的状况）
        if(root2 == null) return true;
        if(root1 == null) return false;
        //判断首节点的值，然后root1与root2的左子树，然后root1与root2的右子树
        return root1.val == root2.val  &&  isSame(root1.left, root2.left)  &&  isSame(root1.right, root2.right);
    }
    
    //方法一：递归的方式（利用深度优先遍历的思想）
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        //判断root1和root2是否为null（空树不是任意一个树的子结构）
        if(root1 == null || root2 == null) return false;
        //如果首结点不相等，则依次比较左子树、右子树与root2的关系
        return isSame(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right,root2);
    }

方法二：层次遍历（利用的是广度优先遍历的思想）

    //判断结构相同必须需要的函数
    public boolean isSame(TreeNode root1,TreeNode root2){
        //如果root2为空，则为true（不需要考虑root1的状况）
        if(root2 == null) return true;
        if(root1 == null) return false;
        //判断首节点的值，然后root1与root2的左子树，然后root1与root2的右子树
        return root1.val == root2.val  &&  isSame(root1.left, root2.left)  &&  isSame(root1.right, root2.right);
    }
    //方法二：层次遍历的方式（利用广度优先遍历的思想）
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        //判断root1和root2是否为null（空树不是任意一个树的子结构）
        if(root1 == null || root2 == null){
            return false;
        }
        //队列（先进先出的特性）
        Queue<TreeNode> queue = new LinkedList<>();
        //把root1放入队列中
        queue.offer(root1);
        //判断队列是否为null
        while(!queue.isEmpty()){
            //取出队列中的结点
            TreeNode cur = queue.poll();
            //判断该结点是否和root相等
            if(isSame(cur, root2)) return true;
            else{
                //不相等则把该结点的不为空的左右子节点放入队列中
                if(cur.left != null) queue.offer(cur.left);
                if(cur.right != null) queue.offer(cur.right);
            }
        }
        return false;
    }