思路：

题目的主要信息：

• t1中含有t2的拓扑结构，即t2是t1的子树

方法一：先序递归法

具体做法：

对t1的每个结点递归遍历（先序），寻找是否有这样的子树，而寻找是否有子树的时候也是用递归，但这次是t1与t2同步先序遍历，遍历完一个t2或者有不相等的结点为止。

class Solution {
public:
    bool function(TreeNode* root1, TreeNode* root2){
        if(root1 == NULL && root2 != NULL)  //当一个结点存在另一个不存在时
            return false;
        if(root1 != NULL && root2 == NULL) 
            return false;
        if(root1 == NULL && root2 == NULL)  //两个都为空则返回
            return true;
        if(root1->val != root2->val)
            return false;
        return function(root1->left, root2->left) && function(root1->right, root2->right);
    }
    bool isContains(TreeNode* root1, TreeNode* root2) {
        if(root1 == NULL && root2 != NULL)
            return false;
        if(root1 == NULL || root2 == NULL)
            return true;
        bool flag1 = function(root1, root2);  //递归比较
        bool flag2 = isContains(root1->left, root2);  //递归树1的每个结点
        bool flag3 = isContains(root1->right, root2);
        return flag1 || flag2 || flag3;
    }
};

复杂度分析：

• 时间复杂度：$O\left(nm\right)O(nm)$O(nm)，两个树结点数相乘
• 空间复杂度：$O\left(nm\right)O(nm)$O(nm)，两个递归栈深度相乘(当树退化成链表时，递归栈最大）

方法二：中序遍历法

具体做法：

与先序遍历类似，只不过递归时遵循先左再中后右的思想。

class Solution {
public:
    bool function(TreeNode* root1, TreeNode* root2){
        if(root1 == NULL && root2 != NULL)  //当一个结点存在另一个不存在时
            return false;
        if(root1 != NULL && root2 == NULL)
            return false;
        if(root1 == NULL && root2 == NULL)  //两个都为空则返回
            return true;
        bool flag1 = function(root1->left, root2->left);
        bool flag2 = root1->val == root2->val;
        bool flag3 = function(root1->right, root2->right);
        return flag1 && flag2 && flag3;
    }
    bool isContains(TreeNode* root1, TreeNode* root2) {
        if(root1 == NULL && root2 != NULL)
            return false;
        if(root1 == NULL || root2 == NULL)
            return true;
        bool flag1 = isContains(root1->left, root2);  //递归树1的每个结点
        bool flag2 = function(root1, root2);  //递归比较
        bool flag3 = isContains(root1->right, root2);
        return flag1 || flag2 || flag3;
    }
};

复杂度分析：

• 时间复杂度：$O\left(nm\right)O(nm)$O(nm)，两个树结点数相乘
• 空间复杂度：$O\left(nm\right)O(nm)$O(nm)，两个递归栈深度相乘