专栏首页猿人谷树的子结构

树的子结构

题目:输入两棵二叉树A和B,判断B是不是A的子结构。

二叉树结点的定义如下:

struct BinaryTreeNode
{
    int             m_nValue;
    BinaryTreeNode *m_pLeft;
    BinaryTreeNode *m_pRight;
};

例如图中的两棵二叉树,由于A中有一部分子树的结构和B是一样的,因此B是A的子结构。

要查找树A中是否存在和树B结构一样的子树,可以分成两步:

  1. 第一步在树A中找到和B的根节点的值一样的结点R;
  2. 第二步再判断树A中以R为根结点的子树是不是包含和树B一样的结构。

第一步在树A中查找与根结点的值一样的结点,这实际上就是树的遍历。递归调用HasSubTree遍历二叉树A。如果发现某一结点的值和树B的头结点的值相同,则调用DoesTreeHavaTree2,做第二步判断。

第二步是判断树A中以R为根结点的子树是不是和树B具有相同的结构。

核心代码:

 1 bool HasSubtree(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2)
 2 {
 3     bool result = false;
 4 
 5     if(pRoot1 != NULL && pRoot2 != NULL)
 6     {
 7         if(pRoot1->m_nValue == pRoot2->m_nValue)
 8             result = DoesTree1HaveTree2(pRoot1, pRoot2);
 9         if(!result)
10             result = HasSubtree(pRoot1->m_pLeft, pRoot2);
11         if(!result)
12             result = HasSubtree(pRoot1->m_pRight, pRoot2);
13     }
14 
15     return result;
16 }
17 
18 bool DoesTree1HaveTree2(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2)
19 {
20     if(pRoot2 == NULL)
21         return true;
22 
23     if(pRoot1 == NULL)
24         return false;
25 
26     if(pRoot1->m_nValue != pRoot2->m_nValue)
27         return false;
28 
29     return DoesTree1HaveTree2(pRoot1->m_pLeft, pRoot2->m_pLeft) &&
30         DoesTree1HaveTree2(pRoot1->m_pRight, pRoot2->m_pRight);
31 }

注意在使用指针的时候一定要注意边界条件,即检查空指针。当树A或树B为空的时候,定义相应的输出。如果没有检查并做相应的处理,程序非常容易崩溃。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 分布式计算Hadoop简介

    Hadoop是什么:Hadoop是一个开发和运行处理大规模数据的软件平台,是Appach的一个用java语言实现开源软件框架,实现在大量计算机组成的集群中对海量...

    猿人谷
  • 顺序循环队列

    1 //循环队列的顺序存储表示与实现 2 3 #include <stdio.h> 4 #include <stdlib.h> 5 6 /**...

    猿人谷
  • ios 开发,通讯录信息调用常用方法,这个比较全,不用再整理了

    ABAddressBookRef addressBook = ABAddressBookCreate(); CFArrayRef results = ...

    猿人谷
  • 24.【Kevin聊敏捷】XP极限编程之12最佳实践(四)

    极限编程要求至少有一名实际的客户代表在整个项目开发周期在现场负责确定需求、回答团队问题以及编写功能验收测试。

    开心的Kevin
  • Dubbo服务治理篇——服务只订阅(开发调试)

    1、“只订阅”指的是需要做开发调试的服务提供者,只向注册中心订阅其所依赖的服务,但不向注册中心注册其本身可以提供的服务。

    冰河
  • python的高级数组之稀疏矩阵

    具有少量非零项的矩阵(在矩阵中,若数值0的元素数目远多于非0元素的数目,并且非0元素分布没有规律时,)则称该矩阵为稀疏矩阵;相反,为稠密矩阵。非零元素的总数比上...

    py3study
  • 【一天一大 lee】上升下降字符串 (难度:简单) - Day20201125

    在任何一步中,如果最小或者最大字符不止一个,你可以选择其中任意一个,并将其添加到结果字符串。

    前端小书童
  • 腾讯游戏DBA利刃 - SQL审核工具介绍

    作者介绍 ? 韩全安(willhan) 华中科技大学,硕士,现代数据库方向。2013年毕业,就职于腾讯到今,工作项目:TMySQL、SQL审核、InnoDB列压...

    数据和云
  • Android Studio 3.1无法导入模块的解决办法

    3月份Android Studio 3.1版正式发布,谁知新版本搞出了新问题,譬如导入已有的模块,Android Studio...

    用户4464237
  • 记一次漏洞挖掘实战之木桶短板

    那mitmproxy+pyppeteer的方法就用不了了 且登陆失败后出现了验证码

    HACK学习

扫码关注云+社区

领取腾讯云代金券