题目练习之二叉树那些事儿


♥♥♥~~~~~~欢迎光临知星小度博客空间~~~~~~♥♥♥

♥♥♥零星地变得优秀~也能拼凑出星河~♥♥♥

♥♥♥我们一起努力成为更好的自己~♥♥♥

♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥

♥♥♥如果有什么问题可以评论区留言或者私信我哦~♥♥♥



知道了二叉树的结构和一些基本操作~这一篇博客是一些关于二叉树的OJ练习题~

练习1:单值二叉树

力扣——965单值二叉树

题目

题目中给出了单值二叉树的含义就是二叉树每一个结点保存的数据相等,函数返回值是bool类型,如果是单值二叉树就返回true,否则返回false。同时题目也给出了它定义的二叉树

思路

既然这里涉及到保存数据的比较,那么肯定需要遍历我们的二叉树了,具体怎么比较呢?我们给出思路~

思路:

让根结点分别与左右孩子结点(孩子结点要不为空)数据比较~如果不相等就返回false~(这里根结点与左右孩子结点比较,就不需要左右孩子结点之间进行比较了,如果【根结点==右孩子结点】&&【根结点==右孩子结点】那么【左孩子结点==右孩子结点】

处理特殊情况:

如果根结点为空,return true;

依次递归比较树的左右子树

代码


bool isUnivalTree(struct TreeNode* root) {
    if(root == NULL)
    {
        return true;
    }
    //根结点分别与不为空左右孩子结点数据比较
    //不相等返回false
    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));
}

提交通过~再一次体会到了二叉树递归的魅力~

练习2:相同的树

力扣——100相同的树

题目

这个题目希望我们判断两颗树是不是相同的,二叉树相同也就是它们相对应的结点保存的数据相同~

思路

思路:

这个题同样是递归比较的方法,比较两颗树相对应的结点是否相同,如果不相同就返回false

处理特殊情况:

如果两个结点都为空 return true;

如果只有一个结点为空 return false;

依次递归比较两颗树的左右子树

代码


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);
}

提交通过~

练习3:另外一棵树的子树

力扣——另外一棵树的子树

题目

这里是不是就与上一个题目有相通的地方,如果判断一个树是不是另外一棵树的子树,我们是不是也就可以从根结点开始遍历另外一棵树与树进行比较判断是不是相同的树,进而判断是不是子树

思路

从根结点root开始判断,两颗树是不是相同的树,如果不是将左右子树与subRoot进行判断是不是相同的树~

注意:

当根结点为NULL,说明两棵树一定不是相同的树,那么subRoot也就不是root的子树,返回false。

代码

我们这里就可以直接把判断是不是相同的树的代码拿过来~


 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);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
    if(root == NULL)
    {
        return false;
    }
    //两颗树相同是子树
    if(isSameTree(root , subRoot))
    {
        return true;
    }
    //递归遍历判断左右子树
    //只要有一个满足就是
    return (isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot));
}

提交通过~

练习4:对称二叉树

力扣——101对称二叉树

题目

这里需要我们判断是不是轴对称图形,不是判断左右子树相同,这个题应该怎么做呢?

思路

有了前面两题的基础,相信这一个题目也就是手到擒来~

思路:如果root为NULL,直接返回true。接着我们只需要判断左右子树是不是对称的树,这里的对称也就说明左子树的左结点保存的数据等于右子树的右结点保存的数据左子树的右结点保存的数据等于右子树的左结点保存的数据。

(判断一个树是否对称,首先要判断左右孩子是否对称相等,还需要判断左孩子的左子树是否和右孩子的右子树对称,左孩子的右子树是否和右孩子的左子树对称。)

代码


 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->right) && isSameTree(p->right,q->left);
}
bool isSymmetric(struct TreeNode* root) {
    if(root == NULL)
    {
        return true;
    }
    //比较左右子树
    if(isSameTree(root->left,root->right))
    {
        return true;
    }
    //else与最近的if搭配
    else
    {
        return false;
    }
}

提交通过~

今天的二叉树题目练习结束,再一次体会到了递归的暴力美学~


♥♥♥本篇博客内容结束,期待与各位优秀程序员交流,有什么问题请私信♥♥♥

♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥


本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/910176.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

K8S篇(基本介绍)

目录 一、什么是Kubernetes? 二、Kubernetes管理员认证(CKA) 1. 简介 2. 考试难易程度 3. 考试时长 4. 多少分及格 5. 考试费用 三、Kubernetes整体架构 Master Nodes 四、Kubernetes架构及和核心组件 五、Kubernetes各个组件及功…

webrtc前端播放器完整案例

https://download.csdn.net/download/jinhuding/89961792

深圳新世联:氢能中的气体传感器应用

氢能作为一种替代能源,被认为是破解能源危机,构建清洁低碳、安全高效现代能源体系的新密码。氢能的开发与利用正在引发一场深刻的能源革命。在2024年《政府工作报告》中,“加快前沿新兴氢能产业发展”这一重要任务被明确提出。据预测&#xf…

电源完整性测试解决方案

电源完整性测试 RIGOL MSO5000电源完整性测试 引言 在过去数十年间,电子行业飞速发展,产品功能不断强大,特性日益丰富,为我们的生活带来了现代化的便利与享受。然而,随着越来越多的产品依赖微控制器来提供优异性能和…

高阶函数--python

高阶函数应当满足至少下面一个条件: 接受一个或多个函数参数 输出一个函数 下面用一个例子来理解高阶函数。 一、高阶函数 先看一个简单的函数 例一: 例二: 是高阶函数,因为满足条件,返回一个函数 并且有闭包&a…

Chrome与火狐哪个浏览器的隐私追踪功能更好

当今数字化时代,互联网用户越来越关注在线隐私保护。浏览器作为我们探索网络世界的重要工具,其隐私追踪功能的强弱直接影响到个人信息的安全。本文将对比Chrome和Firefox这两款流行的浏览器,在隐私追踪防护方面的表现,并探讨相关优…

详细分析WebStorageCache 基本知识

目录 1. 基本知识2. Demo 1. 基本知识 相关的源码如下:web-storage-cache WebStorageCache 是一个用于扩展 HTML5 的 localStorage 和 sessionStorage 的库,增加了超时时间管理和序列化功能。它可以存储 JSON 对象,并且在存储数据时可以方便…

AJ-Report:一款开源且非常强大的数据可视化大屏和报表工具

嗨,大家好,我是小华同学,关注我们获得“最新、最全、最优质”开源项目和工作学习方法 AJ-Report是一个基于Java的开源报表工具,它集成了ECharts、Ant Design Vue等前端技术,致力于为企业提供一站式的数据可视化解决方案…

K3梅林系统 强制刷机方法

对于梅林系统升级过过程中出现的无限重启卡屏的解决方案 黄色字体对应于K3 目前机器 主要分成两个关键步骤:第一、进CFE;第二、用TFTP传入文件进行刷机。 第一: 1硬件网线直接连接K3路由LAN口。 2带有无线网卡的电脑需要屏蔽掉无线网卡&…

数据结构 ——— 链式二叉树oj题:相同的树

目录 题目要求 手搓两个链式二叉树 代码实现 题目要求 给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。 手搓两个链式二叉树 代码演示&…

对标 Windows Copilot 的 UOS AI,升级后更能打了

进入 2024 年,AI 应用迎来大爆发,不仅各类应用纷纷宣称“AI 赋能”,操作系统也不例外。前有 Windows Copilot,后有 Apple Intelligent,手机行业更是积极,各种 AI 手机纷纷发布。国产信创系统自然也不甘落后…

leetcode912.排序数组的题解

题目描述: 题目要求在不使用任何内置函数的情况下解决问题,时间复杂度为 O(nlog(n))。 笔者使用了快速排序,但是直接使用最原始的快速排序,有些特殊的测试用例会超时。 1)如果数组本身基本有序,则使用原始…

迷你版VFB,极简的Freebasic开发IDE-VB7-vb6编程开发

支持Freebasic, Js, vbs, Html5开发,可以发布成控制台程序,EXE,标准DLL,OCX控件,网站 类似Vscode, Aardio,按键精灵一样的开发工具。 本来芳芳只是想做个按键精灵办公小工具,结果一下小心搞了一…

【综合案例】使用React编写B站评论案例

一、效果展示 默认效果,一开始默认按照最热进行排序 发布了一条评论 按照最新进行排序 按照最新进行排序 二、效果说明 页面上默认有3条评论,且一开始进入页面的时候是按照点赞数量进行倒序排列展示,可以点击【最热 、最新】进行排序的切换。…

SSL证书申请终极指南

SSL验证是确认网站或服务器提供的SSL 证书的真实性和有效性的过程。 SSL证书验证是确认网站或服务器提供的SSL证书的真实性和有效性的过程。SSL证书是用于在客户端(例如Web浏览器)和服务器之间建立安全连接的数字证书。它们对于确保通过互联网传输的数据…

处理PhotoShopCS5和CS6界面字体太小

处理PhotoShop CS6界面字体太小 背景:安装PhotoShop CS6后发现无法调大字体大小,特别是我的笔记本14寸的,显示的字体小到离谱。 百度好多什么降低该电脑分辨率,更改电脑的显示图标大小,或者PS里的首选项中的界面设置。…

python中t是什么意思

python中t是什么意思? python中t指的是“\r”:回车符,返回到这一行的开头,return的意思。 其他相关: \n:换行符,到下一行的同一位置,纵坐标相同,new line的意思。 \t…

python项目实战---使用图形化界面下载音乐

音乐下载 设计思路: 设计界面编写爬虫代码绑定爬虫打包exe文件 这个是最终的设计成果,所有的下载歌曲都在“下载mp3”文件夹里面 完整代码 逻辑代码 import os.path import reimport requests from PyQt5.QtWidgets import QApplication,QWidget,QM…

Linux(inode + 软硬链接 图片+大白话)

后面也会持续更新,学到新东西会在其中补充。 建议按顺序食用,欢迎批评或者交流! 缺什么东西欢迎评论!我都会及时修改的! 在这里真的很感谢这位老师的教学视频让迷茫的我找到了很好的学习视频 王晓春老师的个人空间…

从0开始深度学习(24)——填充和步幅

1 填充 在上一节中,我们的卷积步骤如下: 可以发现输入是 3 3 3\times3 33,输出是 2 2 2\times2 22,这样可能会导致原始图像的边界丢失了许多有用信息,如果应用多层卷积核,累积丢失的像素就更多了&#…