专栏首页大白技术控的技术自留地C++版 - 剑指offer 面试题18: 树的子结构(LintCode 245.Subtree) 题解

C++版 - 剑指offer 面试题18: 树的子结构(LintCode 245.Subtree) 题解

题目: 树的子结构

  • 热度指数:9608 时间限制:1秒 空间限制:32768K

提交网址: http://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88?tpId=13&tqId=11170

http://www.lintcode.com/zh-cn/problem/subtree/ (难度: Easy)

题目描述

输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)

思路:

要判断二叉树 A 中是否存在和树 B 结构一样的子结构,可以分成两步: 1.在树 A 中找到和 B 的根结点的值一样的结点R; 2.再判断树 A 中以 R 为根结点的子树是不是包含和树 B 一样的结构。

AC代码:

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    bool Tree1HaveTree2(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        if(pRoot2 == NULL) return true;
        if(pRoot1 == NULL) return false; // 前两个递归出口条件的顺序有影响
        if(pRoot1->val != pRoot2->val) return false;
        return (Tree1HaveTree2(pRoot1->left, pRoot2->left))&&(Tree1HaveTree2(pRoot1->right, pRoot2->right));        
    }
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        bool res = false;
        if(pRoot1 != NULL && pRoot2 != NULL)
        {
        if(pRoot1->val == pRoot2->val) res = Tree1HaveTree2(pRoot1, pRoot2);
        if(res == false) res = HasSubtree(pRoot1->left, pRoot2);
        if(res == false) res = HasSubtree(pRoot1->right, pRoot2);    
        }
        return res;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 史上最强IDE集成开发环境——Code::Blocks简介及安装

    Code::Blocks采用两种方法的版本命名,这一点大家需要了解,以免搞胡涂了。

    Enjoy233
  • 用PHP解决一个有趣的字符串问题

    "a;with( rath ):solve;with(( raeem );with(autoBT);bbb";

    Enjoy233
  • C++版 - LeetCode 145: Binary Tree Postorder Traversal(二叉树的后序遍历,迭代法)

    Total Accepted: 96378 Total Submissions: 271797 Difficulty: Hard

    Enjoy233
  • 趣图:程序员的自尊

    程序员的自尊 ↓↓↓ ? 英文:CommitStrip 汉化:Ray@程序员的那些事 觉得本文对你有帮助?请分享给更多人。

    程序员宝库
  • RocketMQ入门案例【面试+工作】

    Java帮帮
  • python: pop函数

    JNingWei
  • 作为一个0基础的python程序员,我们应该怎样进行自我提升?

    一提起程序员,很多人的第一印象是:格子衬衫,黑框眼镜,长期熬夜的黑眼圈,空洞无神的眼睛,面容呆滞,神情木讷。总结起来就是:人傻钱多死得早。

    原来是泽镜啊
  • 你与其他程序员可能常犯的 6 个错误

    你与其他程序员可能常犯的 6 个错误  我担任 CTO 已经有一段时间了,我觉得这是一个非常好的锻炼机会,因为我不仅可以编写代码,还要带领团队,管理项目,设计架...

    用户1289394
  • iOS面试题:事件传递和响应机制

    判断点在不在当前view上(方法调用者的坐标系上)如果返回YES,代表点在方法调用者的坐标系上;返回NO代表点不在方法调用者的坐标系上,那么方法调用者也就不能处...

    猿_人类
  • jQuery源码解析之$.queue()、$.dequeue()和jQuery.Callbacks()

    前言: queue()方法和dequeue()方法是为 jQuery 的动画服务的,目的是为了允许一系列动画函数被异步调用,但不会阻塞程序。

    进击的小进进

扫码关注云+社区

领取腾讯云代金券