1、思路

• 带空节点的前中后序遍历都可以唯一确定一棵二叉树，要判断一棵树是否包含另一棵树，我们可以分别遍历两棵树生成字符串，对比其中一个字符串是否包含另一个字符串即可；

• 利用string自带的find()方法判断包含关系，string::npos表示不存在的位置；

• 时间复杂度为 $O(n + m)$ ，空间复杂度为 $O(n + m)$，其中 $n$ 和 $m$ 分别是 $t1$ 和 $t2$ 中节点的数目。

2、代码

class Solution {
public:
    void dfs(TreeNode* t, string& s)    //带空节点的前序遍历
    {
        if (t == nullptr)
        {
            s += 'x';                   //若节点为空，则用x表示，任何其他字母也行
            return;
        }

        s += t->val + '0';
        dfs(t->left, s);
        dfs(t->right, s);
    }

    bool checkSubTree(TreeNode* t1, TreeNode* t2) {
        string s1 = "", s2 = "";

        dfs(t1, s1), dfs(t2, s2);       //构造代表两棵树的字符串

        if (s1.find(s2) != string::npos)//判断 s1 是否包含 s2
        {
            return true;
        }
        else
        {
            return false;
        }
    }
};