【数据结构】单值二叉树 & 相同的树 & 翻转二叉树(五)

这篇具有很好参考价值的文章主要介绍了【数据结构】单值二叉树 & 相同的树 & 翻转二叉树(五)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

  目录

一,单值二叉树

题目详情:

解法:父子比较法

解题思路:

思路实现:

源代码:

二,相同的树

题目详情:

解法:比较法

解题思路:

思路实现:

源代码:

三,翻转二叉树

解法:替换法

解题思路:

思路实现:

源代码:


一,单值二叉树

题目详情:

如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树

只有给定的树是单值二叉树时返回 true;否则返回 false;

提示:

1,给定树的结点树范围是【1,100】

2,每个结点的值都是整数,范围为【0,99】

示例1:

【数据结构】单值二叉树 & 相同的树 & 翻转二叉树(五),数据结构,算法,c语言,开发语言,排序算法

输入:nums = [1,1,1,1,1,NULL,1 ]

输出:true

示例2:

【数据结构】单值二叉树 & 相同的树 & 翻转二叉树(五),数据结构,算法,c语言,开发语言,排序算法

输入:nums = [2,2,2,5,2]

输出:false

解法:父子比较法

解题思路:

以上图为例:要判断根结点为(2)的二叉树是否为单值二叉树可以分解为(2)的左右子树是否为单值二叉树,这就很符合递归思路可以用递归解决;【(2)= 左子树 && 右子树】

判断条件:

当结点为NULL时返回 true

当子结点存在时,并且与父亲结点的值不相同时返回 false;

思路实现:

首先要判空:

//判断空
if(root==NULL)
{
    return true;
}

 当结点为空时不影响父亲孩子之间的关系;

然后判断孩子,父亲之间的值的关系:

//判断孩子与父亲的值
if(root->left && root->val!=root->left->val)
{
    return false;
}
if(root->right && root->val!=root->right->val)
{
    return false;
}

 判断孩子,父亲所对应的值是否相同;

大事化小:以上条件都满足时,还需左右子树是否为单值二叉树,只有当左右子树都为单值二叉树时才为 true;

//化为两颗子树是否为单值树
return isUnivalTree(root->left) && isUnivalTree(root->right);

 要用逻辑与,需要双方为真时才返回 true;

源代码:

bool isUnivalTree(struct TreeNode* root){
    //判断空
    if(root==NULL)
    {
        return true;
    }
    //判断孩子与父亲的值
    if(root->left && root->val!=root->left->val)
    {
        return false;
    }
    if(root->right && root->val!=root->right->val)
    {
        return false;
    }
    //化为两颗子树是否为单值树
    return isUnivalTree(root->left) && isUnivalTree(root->right);
}

我们可以用示例来演算一遍,流程也是这样的;

像这种递归题目要演算其过程需要画图,这样才是最直观的;

二,相同的树

题目详情:

给你两棵二叉树的根结点 p 和 q ,编写一个函数来检验这两棵树是否相同;

如果两个树在结构上相同,并且结点具有相同的值,则认为它们是相同的;

提示:

两棵树上的结点数目都在范围【0,100】内

-104<=Node.val<=10 

示例1:

【数据结构】单值二叉树 & 相同的树 & 翻转二叉树(五),数据结构,算法,c语言,开发语言,排序算法

输入:p = [ 1,2,3 ],q = [ 1,2,3 ]

输出:true

示例2:

【数据结构】单值二叉树 & 相同的树 & 翻转二叉树(五),数据结构,算法,c语言,开发语言,排序算法

输入:p = [ 1,2 ],q = [ 1,2 ]

输出:false

示例3:

【数据结构】单值二叉树 & 相同的树 & 翻转二叉树(五),数据结构,算法,c语言,开发语言,排序算法

输入:p = [ 1,2,1 ],q = [ 1,2,2 ]

输出:false

解法:比较法

解题思路:

要判断两棵树是否一致,要考虑的是他们的结点是否都存在,结点对应的值是否相同;

以上图为例:根结点相同了,还要判断其左右子树是否也相同,然后层层往下,这道题也是用递归思想;

思路实现:

首先要判断他们的结点是否对应存在:

    //双方都为空
    if(p==NULL && q==NULL)
    {
      return true;
    }
    //一方为空另一方不为空
    if((p==NULL || q==NULL) 
    {
      return false;
    }

当双方对应的结点都为空时返回 true

当双方对应的结点只有一方为空,另一方不为空时,返回 false

然后判断它们对应的结点的值的情况:

    //判断所对应的值是否相同
    if(p->val != q->val)
    {
      return false;
    }

当所对应的值不相等则返回 false;

大事化小:当以上条件都满足时,还需要判断这两棵树所对应的左右子树是否相同;

    //判断其对应的左右子树是否也相同
    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);

源代码:

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    //双方都为空
    if(p==NULL && q==NULL)
    {
      return true;
    }
    //一方为空另一方不为空
    if((p==NULL || q==NULL) 
    {
      return false;
    }
    //判断所对应的值是否相同
    if(p->val != q->val)
    {
      return false;
    }
    //判断其对应的左右子树是否也相同
    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}

这就是判断两颗二叉树是否相同问题的解题思路了,还是利用递归;

三,翻转二叉树

题目详情:

给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点

示例1:

【数据结构】单值二叉树 & 相同的树 & 翻转二叉树(五),数据结构,算法,c语言,开发语言,排序算法

输入:root = [ 4,2,7,1,3,6,9 ]

输出:[ 4 7 2 9 6 3 1 ]

示例2:

【数据结构】单值二叉树 & 相同的树 & 翻转二叉树(五),数据结构,算法,c语言,开发语言,排序算法

输入:root = [ 2,1,3 ]

输出:[ 2,3,1]

示例3:

输入:root = [ ]

输出:[ ]

解法:替换法

解题思路:

翻转翻转所谓翻转其实就是将左右子树换个位置而已,直接将其交换,层层交换下去直至NULL,用递归来实现;

思路实现:

首先还是判空,如果为空直接返回NULL即可;

然后直接交换左,右子树,再让其左,右子树也如此下去,就完成了对整颗树的翻转了,在返回根结点即可;

源代码:

void swap(struct TreeNode** left,struct TreeNode** right)
{
    struct TreeNode* tmp=*left;
    *left=*right;
    *right=tmp;
}

struct TreeNode* invertTree(struct TreeNode* root){
    //判空
    if(root==NULL)
    {
        return NULL;
    }
    //交换
    swap(&root->left,&root->right);
    //左子树翻转
    invertTree(root->left);
    //右子树翻转
    invertTree(root->right);
    return root;
}

基本上与二叉树相关的练习都要使用递归思想前期培养递归思路最好就是画图解析,这个很重要,画图能让我们更直观的感受结点之间的关系,特别是感受那个返回的过程领悟其中的奥妙,久而久之我们对于递归的思路就更加清晰了,不至于摸不着北;

第五阶段就到这里了,这阶段带大家刷道些题目来感受一下二叉树的魅力!

后面博主会陆续更新;

如有不足之处欢迎来补充交流!

完结。。文章来源地址https://www.toymoban.com/news/detail-725687.html


到了这里,关于【数据结构】单值二叉树 & 相同的树 & 翻转二叉树(五)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C语言题解】 | 965. 单值二叉树

    提示: 给定树的节点数范围是 [1, 100]。 每个节点的值都是整数,范围为 [0, 99] 。 这个题目我们通过分治思想来解题: 首先传入的是根节点 其次判断根节点是否有左子树和右子树,若存在则判断左右子树的值是否于根节点的值相同(不同则返回false,相同则继续) 若正确,

    2024年01月21日
    浏览(32)
  • 【数据结构-二叉树】二叉树

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月07日
    浏览(47)
  • 数据结构:搜索二叉树 | 平衡二叉树

    博客写的代码都放在这里:gitee仓库链接 1.二叉搜索树 1.1.基本概念 二叉搜索树又称二叉排序树, 可以为空,如果不为空具有以下性质的二叉树 : 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的

    2024年01月23日
    浏览(57)
  • 【数据结构和算法】--- 二叉树(3)--二叉树链式结构的实现(1)

    在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入,且为了方便后面的介绍,此处手动快速创建一棵简单的二叉树,快速进入二叉树操作学习,等二叉树结构了解的差不多时,我们反过头再来研

    2024年01月25日
    浏览(59)
  • 【数据结构】二叉树——链式结构

    目录  一、前置声明 二、二叉树的遍历 2.1 前序、中序以及后序遍历 2.2 层序遍历 三、节点个数以及高度 3.1 节点个数 3.2 叶子节点个数 3.3 第k层节点个数 3.4 二叉树的高度/深度 3.5 查找值为x的节点 四、二叉树的创建和销毁 4.1 构建二叉树 4.2 二叉树销毁 4.3 判断二叉树

    2024年02月16日
    浏览(44)
  • 【数据结构】二叉树——顺序结构

    由于每个节点都 只有一个父节点 ,所以我们可通过双亲来表示一棵树。具体方式通过 数组的形式 实现。 根节点的下标为0 按照层序从上到下排序 每层从左向右递增 表示形式: 二维数组 数据的列标为0 ,只需确定行标,即可锁定位置 根节点的父节点下标为 -1 列标为1存父节

    2024年02月02日
    浏览(55)
  • 数据结构-二叉树-二叉树左右孩子交换(递归)

     注:本文采用队列和递归的算法进行创建和层次遍历。同时不能采用BFS和DFS,因为需要把当前根节点的左孩、右孩勾链并输入才能递归下一个根节点; 队列用于存储此时应该递归的根节点; 格式:每一行尾不能有空格; Description 根据输入利用二叉链表创建二叉树,并将所

    2024年02月04日
    浏览(50)
  • 【数据结构】二叉树链式结构

    🚀write in front🚀 📜所属专栏:初阶数据结构 🛰️博客主页:睿睿的博客主页 🛰️代码仓库:🎉VS2022_C语言仓库 🎡您的点赞、关注、收藏、评论,是对我最大的激励和支持!!! 关注我,关注我,关注我 , 你们将会看到更多的优质内容!!   在之前的二叉树的顺序结

    2024年02月03日
    浏览(39)
  • 【数据结构】二叉树的介绍和二叉树堆

    💓作者简介: 加油,旭杏,目前大二,正在学习 C++ , 数据结构 等👀 💓作者主页:加油,旭杏的主页👀 ⏩本文收录在:再识C进阶的专栏👀 🚚代码仓库:旭日东升 1👀 🌹欢迎大家点赞 👍 收藏 ⭐ 加关注哦!💖        树这一概念,在我们刚开始听说的时候会觉得

    2024年01月20日
    浏览(50)
  • 数据结构之二叉树和平衡二叉树

    1、二叉树: 2、平衡二叉树:

    2024年04月17日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包