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

/*
描述
给定彼此独立的两棵二叉树，判断 t1 树是否有与 t2 树拓扑结构完全相同的子树。
设 t1 树的边集为 E1，t2 树的边集为 E2，若 E2 等于 E1 ，则表示 t1 树和t2 树的拓扑结构完全相同。
示例1
输入：
{1,2,3,4,5,6,7,#,8,9},{2,4,5,#,8,9}
复制
返回值：
true
复制
备注：
1 \leq n \leq 5000001≤n≤500000
*/

#include<iostream>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    /**
     *
     * @param root1 TreeNode类
     * @param root2 TreeNode类
     * @return bool布尔型
     */
    bool isContains(TreeNode* root1, TreeNode* root2) {
        // write code here
        if (root2 == NULL) return true;
        if (root1 == NULL) return false;
        return (isSubTree(root1, root2) || isContains(root1->left, root2) || isContains(root1->right, root2));
    }

    bool isSubTree(TreeNode* root1, TreeNode* root2) {
        if (root1 == NULL && root2 == NULL)
            return true;
        if (root1 == NULL || root2 == NULL || (root1->val != root2->val))
            return false;
        return (isSubTree(root1->left, root2->left) && isSubTree(root1->right, root2->right));
    }

};