• 剑指offer——JZ26 树的子结构 解题思路与具体代码【C++】


    一、题目描述与要求

    树的子结构_牛客题霸_牛客网 (nowcoder.com)

    题目描述

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

    假如给定A为{8,8,7,9,2,#,#,#,#,4,7},B为{8,9,2},2个树的结构如下,可以看出B是A的子结构

    数据范围:

    0 <= A的节点个数 <= 10000

    0 <= B的节点个数 <= 10000

    示例

    示例1:

    输入:{8,8,7,9,2,#,#,#,#,4,7},{8,9,2}

    返回值:true

    示例2:

    输入:{1,2,3,4,5},{2,4}

    返回值:true

    示例3:

    输入:{1,2,3},{3,1}

    返回值:false


    二、解题思路

    根据题目描述,我们需要判断B树是否为A树的子树。

    首先题目规定了“空树不是任意一个树的子结构”,所以我们先判断B树是否为空树,是的话直接返回false;

    然后如果A是空树且B不是空树的话,那么B肯定不是A的子树,也返回false;

    但是如果A和B都为空或者A不为空B为空的情况下,则B就是A的子树,返回true;(这里的空,可应该解释为空节点)

    若A树B树都不为空,则我们就需要对两个树进行遍历,然后比较,我们想要判断B树是否为A树的子树,那就需要从根结点开始,以每个结点为“根结点”然后跟B树进行比较。【这是因为B树不一定是从A的根结点开始的,所以在当前结点不符合的情况下,我们依次将左节点与右节点作为“根结点”与B树进行比较】

    如果根结点的值相同,则去判断左子树与右子树是否相同,都相同就代表B是A的子树,只要有不同则就需要我们继续往下找,也就是换一个结点为“根结点”,然后与B树继续比较。

    直至找到与B树相同的结点或者A树遍历结束。

    最后对所设置的三个标志进行判断。flag1是指以根结点开始与B树比较的结果,flag2是指以左子树的结点为开始与B树比较的结果,flag3是指以右子树的结点为开始与B树比较的结果。三者只需要有一个为真就代表B树是A的子树。【每个比较都是递归的,都是以当前节点为根结点,以此去访问左子树与右子树】


    三、具体代码

    1. class Solution {
    2. public:
    3. bool recursion(TreeNode* pRoot1,TreeNode* pRoot2){
    4. //当一个节点存在另一个不存在时
    5. if(pRoot1==nullptr&&pRoot2!=nullptr) return false;
    6. //两个都为空则返回true
    7. if(pRoot1==nullptr||pRoot2==nullptr) return true;
    8. //比较节点值
    9. if(pRoot1->val!=pRoot2->val) return false;
    10. //递归比较子树
    11. return recursion(pRoot1->left,pRoot2->left) && recursion(pRoot1->right,pRoot2->right);
    12. }
    13. bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
    14. //B为空树
    15. if(pRoot2==nullptr) return false;
    16. //A为空,B不为空
    17. if(pRoot1==nullptr&&pRoot2!=nullptr) return false;
    18. //A不为空B为空 A,B都为空
    19. if(pRoot1==nullptr||pRoot2==nullptr) return true;
    20. //把当前根结点的二叉树与B树进行递归比较
    21. bool flag1=recursion(pRoot1,pRoot2);
    22. //递归A树的每个结点 分别以每个结点为根结点进行比较
    23. bool flag2=HasSubtree(pRoot1->left,pRoot2);
    24. bool flag3=HasSubtree(pRoot1->right, pRoot2);
    25. return flag1||flag2||flag3;
    26. }
    27. };

  • 相关阅读:
    【从零开始学习Redis | 第五篇】基于布隆过滤器解决Redis的穿透问题
    多显示屏,将Qt程序显示在指定显示器上
    整理了60个 Python 实战例子,拿来即用!
    Spring6整合JUnit5
    数据结构——栈和队列互相实现
    uniapp-css:拼图(不规则图片拼插)、碎片
    外包干了3个月,技术退步明显。。。。。
    工业交换机选购标准,你知道多少?
    每日实用技巧分享:怎么修复老照片?
    Ceph入门到精通-iptables 限制多个ip 的多个端口段访问
  • 原文地址:https://blog.csdn.net/m0_59800431/article/details/133611967