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

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

http://www.nowcoder.com/practice/4eaccec5ee8f4fe8a4309463b807a542

/*
描述
给定彼此独立的两棵二叉树,判断 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));
    }

};
全部评论

相关推荐

07-01 23:23
郑州大学 Java
否极泰来来来来:牛客迟早有高三的
点赞 评论 收藏
分享
Twilight_m...:经典我朋友XXXX起手,这是那种经典的不知道目前行情搁那儿胡编乱造瞎指导的中年人,不用理这种**
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 12:04
毕业生招你惹你了,问一个发薪日来一句别看网上乱七八糟的你看哪个工作没有固定发薪日扭头就取消了面试就问了一句公司都是这个态度吗还搞上人身攻击了...
程序员小白条:呃呃呃,都还没面试,我都不会问这么细,何况通不通过,去不去都另说,你没实力和学历的话,在外面就这样,说实话没直接已读不回就不错了,浪费时间基本上
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务