题解 | #判断t1树中是否有与t2树拓扑结构完全相同的子树#

判断t1树中是否有与t2树拓扑结构完全相同的子树
题意:
给定彼此独立的两棵二叉树，判断 t1 树是否有与 t2 树拓扑结构完全相同的子树。

输出描述
输出true表示t1树的边集为 E1，t2 树的边集为 E2，E2 等于 E1 ，说明 t1 树和t2 树的拓扑结构完全相同。

案例
输入：{1,2,3,4,5,6,7,#,8,9},{2,4,5,#,8,9}
返回值：true

方法一 后序遍历

根据题意能发现t2将会是t1树中的一个子树所以考虑后序遍历做对比,判断t2的后序序列是否包含在t1的后序遍历即可。

bool isContains(TreeNode* root1, TreeNode* root2) {
        // write code here
        vector<int> res1, res2;
        get(root1, res1); // t1的后序遍历
        get(root2, res2); // t2的后序遍历
        for(int i = 0; i < res1.size(); i ++){ // 判断t2是否包含在t1中
            if(res1[i] == res2[0]){ //找到值相等的位置
                int fase = 1;
                for(int j = 0; j < res2.size(); j ++){ // 判断t2是否包含在t1中
                    if(i < res1.size() && res1[i] != res2[j]){
                       fase = 0; break;
                    }
                    i ++;
                }
                if(fase) return true;
            }
        }
        return false;
    }
    void get(TreeNode* rt, vector<int> &v){ // 后序遍历递归
        if(!rt) return;
        get(rt->left, v);
        get(rt->right, v);
        v.push_back(rt->val);
    }

时间复杂度: 遍历两颗树和序列总体复杂度为
空间复杂度: 递归中与vector存储消耗了的空间

方法二 递归

遍历t1树所有节点，当t1数的值与t2数的值相同时,搜索当前t1树的子树与t2树是否相等.

bool isContains(TreeNode* root1, TreeNode* root2) {
        if(!root1) return false; 
        if(root1->val != root2->val) { // 当前t1值与t2值不相等时继续搜索t1左右子树
            bool a = isContains(root1->left, root2);
            bool b = isContains(root1->right, root2);
            return a || b;
        }else{ //值相同时搜索当前t1子树与t2树是否相同
            return dfs(root1, root2);
        }
    }
    bool dfs(TreeNode* r1, TreeNode* r2){
        if(r1->val != r2->val) return false;    //如果两颗树值不同直接false
        bool a = false, b = false;
        if(r1->left && r2->left){ //同时存在左子节点则向左子节点搜索
            if(dfs(r1->left, r2->left)) a = true;
            else a =false;
        }else if(!r1->left && !r2->left) a = true; //他们的叶子结点要相同

        if(r1->right && r2->right){//同时存在右子节点则向左子节点搜索
            if(dfs(r1->right, r2->right)) b = true;
            else b =false;
        }else if(!r1->right && !r2->right) b = true;//他们的叶子结点要相同
        return a && b;
    }

时间复杂度: 最多会将t1树与t2树遍历一遍
空间复杂度: 递归消耗了的空间