题目

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

思路

1. 找到root2.val和root1.val相等的节点
2. 开始往下面找，左节点和左节点一样，右节点和右节点一样
3. 在递归过程中，root2 == null，递归结束（true）；root1 == null（false）

代码

    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        boolean res = false;
        if (root1 != null && root2 != null) {
            if (root1.val == root2.val) {
                res = DoseTree1HasTree2(root1, root2);
            }

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

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

    private boolean DoseTree1HasTree2(TreeNode root1, TreeNode root2) {
        if(root2 == null){
            return true;
        }
        
        if(root1 == null){
            return false;
        }
        
        if(root1.val != root2.val){
            return false;
        }
        
        return DoseTree1HasTree2(root1.left,root2.left) && DoseTree1HasTree2(root1.right,root2.right);
    }