//方法一：可以借鉴之前序列化的题目，如果序列化得到的序列一样就是相同的树

//方法二：用递归来写十分的简洁，我们先从s的根结点开始，跟t比较，如果两棵树完全相同，那么返回true，否则就分别对s的左子结点和右子结点调用递归再次来判断是否相同，只要有一个返回true了，就表示可以找得到。

class Solution {

public:

    bool isSubtree(TreeNode* s, TreeNode* t) {

        //方法二的递归

        if (!s)

            return false;

        if (isSame(s,t))

            return true;

        return isSubtree(s->left,t) || isSubtree(s->right,t);

    }

    bool 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;

        if (s->val == t->val)

            return isSame(s->left,t->left) && isSame(s->right,t->right);

    }

};

//写成两个序列，判断一个序列是否包含另一个序列为子序列

class Solution {

public:

    bool isSubtree(TreeNode* s, TreeNode* t) {

        ostringstream os1, os2;

        serialize(s, os1);

        serialize(t, os2);

        return os1.str().find(os2.str()) != string::npos;

    }

    void serialize(TreeNode* node, ostringstream& os) {

        if (!node) os << ",#";

        else {

            os << "," << node->val;

            serialize(node->left, os);

            serialize(node->right, os);

        }

    }

};