Given two non-empty binary treessandt, check whether treethas exactly the same structure and node values with a subtree ofs. A subtree ofsis a tree consists of a node insand all of this node's descendants. The treescould also be considered as a subtree of itself.

Example 1:
Given tree s:

     3
    / \
   4   5
  / \
 1   2

Given tree t:

   4 
  / \
 1   2

Return true, because t has the same structure and node values with a subtree of s.

Example 2:
Given tree s:

     3
    / \
   4   5
  / \
 1   2
    /
   0

Given tree t:

   4
  / \
 1   2

Return false

.Solution: 把树t serialize，树s各子树serialize并放进hashset，最后看hashset有没有string_t

class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (t == null) {
            return true;
        }
        if (s == null) {
            return false;
        }
        Set<String> hashset = new HashSet<>();
        String string_s = serialize(s, hashset, true);
        String string_t = serialize(t, hashset, false);
        return hashset.contains(string_t);
    }
    private String serialize(TreeNode s, Set<String> hashset, boolean save) {
        if (s == null) {
            return "";
        }
        String string = s.val + "," + serialize(s.left, hashset, save) + "," + serialize(s.right, hashset, save);
        if (save) {
            hashset.add(string);
        }
        return string;
    }

wrong 1: 不存s的子树，直接取得整颗树的string, null时返回“”，eg:

    1          1
   / \        /
  2   3      2       会返回true

    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (t == null) {
            return true;
        }
        if (s == null) {
            return false;
        }

        String string_s = serialize(s);
        String string_t = serialize(t);
        return string_s.contains(string_t);
    }
    private String serialize(TreeNode s) {
        if (s == null) {
            return "";
        }
        String string = s.val + "," + serialize(s.left) + "," + serialize(s.right);

        return string;
    }

wrong 2: 同样做法，不过null时返回"#", eg: 12 2 会返回true

    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (t == null) {
            return true;
        }
        if (s == null) {
            return false;
        }
        String string_s = serialize(s);
        String string_t = serialize(t);
        return string_s.contains(string_t);
    }
    private String serialize(TreeNode s) {
        if (s == null) {
            return "#";
        }
        String string = s.val + "," + serialize(s.left) + "," + serialize(s.right);
        return string;
    }

所以如果不用hashset存所有子树，就要把逗号放在数字前，null时不返回""

public boolean isSubtree(TreeNode s, TreeNode t) {
    return serialize(s).contains(serialize(t)); // Java uses a naive contains algorithm so to ensure linear time, 
                                                // replace with KMP algorithm
}

public String serialize(TreeNode root) {
    StringBuilder res = new StringBuilder();
    serialize(root, res);
    return res.toString();
}

private void serialize(TreeNode cur, StringBuilder res) {
    if (cur == null) {res.append(",#"); return;}
    res.append("," + cur.val);
    serialize(cur.left, res);
    serialize(cur.right, res);
}

Solution 2: 对s每个node，跟t检查是否一样

    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (s == null) return false;
        if (isSame(s, t)) return true;
        return isSubtree(s.left, t) || isSubtree(s.right, t);
    }

    private boolean isSame(TreeNode s, TreeNode t) {
        if (s == null && t == null) return true;
        if (s == null || t == null) return false;

        if (s.val != t.val) return false;

        return isSame(s.left, t.left) && isSame(s.right, t.right);
    }