572. Subtree of Another Tree

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could 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.

// Recursion
bool helper(TreeNode*s, TreeNode* t) {
    if (!s || !t) return s == t;
    return s->val == t->val && helper(s->left, t->left) && helper(s->right, t->right);
}
bool isSubtree(TreeNode* s, TreeNode* t) { // time: (m*n); space: O(m + n)
    if (!s || !t) return s == t;
    return helper(s, t) || isSubtree(s->left, t) || isSubtree(s->right, t);
}

// Serialization Solution
void serialize(TreeNode* node, ostringstream& os) {
    if (!node) os << ",#";
    else {
        os << "," << node->val; // add a char before node value to differentiate the case such as [12] and [2]
        serialize(node->left, os);
        serialize(node->right, os);
    }
}
bool isSubtree(TreeNode* s, TreeNode* t) { // time: O(m + n); space: O(m + n)
    ostringstream os1, os2;
    serialize(s, os1);
    serialize(t, os2);
    return os1.str().find(os2.str()) != string::npos;
}