我在这道题上栽过的坑

第一坑
首先我以为，只要逐一比较各个节点就好了。作为一棵被比较的子树，它应该完全和原树的某个子树相同（包含所有叶子节点），而不是组成某子树的一部分（不包含该子树的所有叶子节点）。所以我写了：

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root1==null&&root2==null) return true;
        if(root1==null||root2==null) return false;
        if(root1.val==root2.val&&
           HasSubtree(root1.left, root2.left)&&
           HasSubtree(root1.right, root2.right))
            return true;
        return HasSubtree(root1.left, root2)||HasSubtree(root1.right,root2);
    }
}

结果显然是错了，因为错的例子中有一个是
{8,8,7,9,2,#,#,#,#,4,7},{8,9,2}
对应输出应该为:
true
你的输出为:
false

Okay，我明白了，你允许root1的子树有多余的叶子节点。

第二坑
于是我改掉了上面代码的第4行，变成了

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root1==null&&root2==null) return true;
        if(root1==null) return false;
        if(root2==null) return true;
        if(root1.val==root2.val&&
           HasSubtree(root1.left, root2.left)&&
           HasSubtree(root1.right, root2.right))
            return true;
        return HasSubtree(root1.left, root2)||HasSubtree(root1.right,root2);
    }
}

蛤，结果又错了！
这，究竟是人性的扭曲，还是道德的沦丧？？
一看题目， 噢

（ps：我们约定空树不是任意一个树的子结构）

原来如此，失敬失敬！！
本来打算写一个漂亮的函数递归自身就行，现在看来不得不把递归的这个写成另一个函数了。否则我无法区分 root2==null 的情况。所以最终答案为。

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root2==null) return false;
        return hasSubtree(root1,root2);
    }

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