树 t 是否等于树 s 的子树

树 t 是否等于树 s 的子树

问题

这个题目说的是，给你两棵二叉树 s 和 t，你要判断 t 是否与 s 的某一棵子树结构相同，并且节点上的值也相等。

比如说，给你的第一棵树 s 是：

     1
    / \
   2   4
  / \
 8  16

给你的第二棵树 t 是：

   2
  / \
 8  16

t 与 s 的一棵子树相等，因此你要返回 true。如果向 s 中再加一个节点 0：

     1
    / \
   2   4
  /  \
 8  16
    /
   0

这个时候，t 就不等于 s 中的任何一棵子树了，因此返回 false。

代码

public class AlgoCasts {

  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  private 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);
  }

  // Time: O(m*n), Space: O(h)
  public boolean isSubtree(TreeNode s, TreeNode t) {
    if (t == null) return true;
    if (s == null) return false;
    return isSameTree(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
  }

  private Map<TreeNode, Integer> map = new HashMap<>();

  private String computeHash(TreeNode t) {
    if (t == null) return "#";
    String left = computeHash(t.left);
    String right = computeHash(t.right);
    String hash = left + t.val + right;
    map.put(t, hash.hashCode());
    return hash;
  }

  private boolean isSub(TreeNode s, TreeNode t) {
    if (t == null) return true;
    if (s == null) return false;
    return map.get(s).equals(map.get(t)) || isSub(s.left, t) || isSub(s.right, t);
  }

  // Time: O(m+n), Space: O(m+n)
  public boolean isSubtreeHash(TreeNode s, TreeNode t) {
    computeHash(s);
    computeHash(t);
    return isSub(s, t);
  }

}