Leetcode572 树t是否为树s的子树

先是原始解法，采用递归的方式，代码如下：

class Solution {
    public boolean isSameTree(TreeNode s, TreeNode t){
        if(s == null && t == null) return true;
        if(s == null || t == null) return false;
        return s.val == t.val && isSameTree(s.left,t.left) && isSameTree(s.right, t.right);
    }
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if(s == null && t!= null) return false;
        if(s != null && t == null) return true;
        else return isSameTree(s,t) || isSubtree(s.left,t) || isSubtree(s.right, t);
    }
}

时间复杂度O(m*n),空间复杂度O(h),h为树的高度。
上面的方法首先要遍历s的每个节点，对于每个节点，t都要遍历一次。
但是，对比两棵树是否相同，不需要一个个节点对比，而是大家有一个唯一标识拿出来对比，这样对比就需要O（1）的时间。比如可以采用把左节点，根结点，右节点的值拼接起来。因此可以采用字符串的hash函数，把整棵树的对比降到O(1)复杂度。因为在构造hash表的时候需要分别遍历一次s和t，所以算法的时间复杂度是O(m+n), 空间复杂度：由于要保存hash表，所以也是O(m+n)；
代码如下：

class Solution {
    Map<TreeNode, Integer> map = new HashMap<>();
    public String computeHash(TreeNode s){
        if(s == null) return "#";
        String left = computeHash(s.left);
        String right = computeHash(s.right);
        String hash = left + s.val + right;
        map.put(s,hash.hashCode());
        return hash;
    }
    //构建计算hash函数的时候有技巧，要返回字符串的形式便于递归的过程中返回值。
    public boolean isSub(TreeNode s, TreeNode t){
        if(s == null) return false;
        if(t == null) return true;
        return map.get(s).equals(map.get(t)) || isSub(s.left,t ) || isSub(s.right, t);
    }
    public boolean isSubtree(TreeNode s, TreeNode t) {
        computeHash(s);
        computeHash(t);
        return isSub(s,t);
    }
}