数据结构刷题训练——二叉树篇(一)
📙作者简介: 清水加冰,目前大二在读,正在学习C/C++、Python、操作系统、数据库等。
📘相关专栏:C语言初阶、C语言进阶、C语言刷题训练营、数据结构刷题训练营、有感兴趣的可以看一看。
欢迎点赞 👍 收藏 ⭐留言 📝 如有错误还望各路大佬指正!
✨每一次努力都是一种收获,每一次坚持都是一种成长✨
目录
前言
📖题目1:翻转二叉树
📖题目2:相同的树
📖题目3:对称二叉树
📖题目4:另一棵树的子树
📖题目5:二叉树的前序遍历
总结
前言
我们学习了二叉树的顺序结构和链式结构,在日常刷题在,我们最常见的就是链式二叉树,刚学习完链式二叉树刷题上手比较难,本期我将继续开始数据结构刷题专栏,为大家提供二叉树(初阶)相关的练习和力扣OJ的经典题目以及题目讲解,以便于大家更容易上手二叉树部分的刷题。
📖题目1:翻转二叉树
题目描述:
题目链接:
翻转二叉树https://leetcode.cn/problems/invert-binary-tree/description/
✨题目解析:
本道题目较为简单,要学会巧妙运用递归解决问题,翻转二叉树也就是翻转它的左子树和右子树,然后不断的向下分,在使用递归时要注意递归结束的条件,确保所有的控件路径都返回值。
代码如下:
struct TreeNode* invertTree(struct TreeNode* root){if(root==NULL){return NULL;}struct TreeNode* left=invertTree(root->left);struct TreeNode* right=invertTree(root->right); root->right=left;root->left=right;return root;
}
📖题目2:相同的树
题目描述:
题目链接:
相同的树https://leetcode.cn/problems/same-tree/description/
✨题目解析:
这道题目的递归思路比上道题复杂一点,主要考察的是对递归的使用以及控制。题目中传进来的是两个树,那要如何去控制递归呢?
两棵树是否相同,主要就是比较对于位置的节点数据是否相同,如果两棵树的每个对应节点都相等,这两棵树就相等,但单纯的判断值是否相等无法做到所有的控件路径都返回值,这里也要考虑特殊情况,当一颗树为NULL,另一颗树不为空,这时就要返回false,两棵树当前节点都为NULL,就返回true。有了这些前提,我们对代码进行实现,那这样写对不对呢?
bool isSameTree(struct TreeNode* p, struct TreeNode* q){if(p==NULL&&q==NULL)//两个都为NULL就返回True{return true;}if(p==NULL||q==NULL)//两棵树都不为NULL为前提{return false;}if(p->val==q->val){return true;}return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}
这样写乍一看没什么问题,但它在力扣上通过不了,例如:
p:[1,2] q:[1,null,2]
你会发现它根本就没递归进去就返回了,只比较了根节点的值。我们需要让它递归到最后,也就是叶子节点,从叶子节点开始。既然正向行不通,那就逆向,如果它们的val不相等就返回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);
}
这样就可以递归到叶子节点,如果递归到最后一直到叶子节点都没有返回false,那就说明递归路径上的节点都相等,如果有一个返回的是false,最后返回的是左子树与右子树取&&的结果,最终一定会返回false。如果节点都相当才会返回true。
例如这棵树:递归从左子树开始,节点2的left递归返回true,right返回也是true,那节点2整体返回就是true,然后开始递归右子树,右子树返回和左子树一样也是true。然后返回到节点1的递归左右子树都为true,那整体就返回true。
📖题目3:对称二叉树
题目描述:
题目链接:
对称二叉树https://leetcode.cn/problems/symmetric-tree/✨题目解析:
这道题的解法和上道题很像,也就是在上道题做了一点进阶。
它让我们判断对称,那我们就可以将这棵树的左子树和右子树分为两棵树,上道题目判断是相同位置的节点相同,我们传的都是p->left,q->left,我们观察一下对称的二叉树,左子树的左孩子节点与右子树的右孩子节点相同,左子树的右孩子与右子树的左孩子相同。
那我们在判断相同时是否就可以这样传值,去比较左子树的左孩子和右子树的右孩子,左子树的右孩子和右子树的左孩子是否相同。
那我们就只需改变一下传的参数即可。我们套用一下上边相同的二叉树的进行变形一下:
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){return isSameTree(root->left,root->right);
}
📖题目4:另一棵树的子树
题目链接:
另一棵树的子树https://leetcode.cn/problems/subtree-of-another-tree/description/
✨题目解析:
判断一颗树是否是另一棵树的子树,还是会用到两棵树是否相等。只不过这道题目需要注意一下开始比较的条件。我们先写一个框架
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){if(root==NULL){return false;}if(root->val==subRoot->val){//开始比较……}return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);//遍历左子树 // 遍历右子树
}
如果完整的树为NULL那就不在需要判断了,直接返回false。然后开始比较root的值是否与subRoot的值相等,如果相等就从值相等的节点位置开始判断两棵树是否相同。在寻找相同值的过程中我们需要遍历二叉树,遍历二叉树最简便的方法就是使用递归,只要root左子树或右子树有一个存在子树相同,那就返回true(所以这里使用 “ || ” )。
注意:只有返回类型为bool类型时才可以进行&&或||的操作
完整代码如下:
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){if(root==NULL){return false;}if(root->val==subRoot->val){if(isSameTree(root,subRoot)) //isSameTree函数使用的是上述题目2的代码{return true;}}return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}
📖题目5:二叉树的前序遍历
题目描述:
题目链接:
二叉树的前序遍历https://leetcode.cn/problems/binary-tree-preorder-traversal/
✨题目解析:
这道二叉树的前序遍历和我们·之前的不太一样,我们需要把遍历的值放在一个数组中,所以首先我们还需要知道二叉树的节点个数才可以创建数组,然后再开始遍历二叉树。
我们可以分两个接口来写:
int* preorderTraversal(struct TreeNode* root, int* returnSize){*returnSize=0; //返回的数组大小int n=TreeSize(root);int* ret=(int*)malloc(sizeof(int)*n);preorder(root,ret,returnSize);//遍历二叉树return ret;//返回数组
}
这里的前序遍历和之前没什么区别,区别就在原本输出的位置需要把数据存到数组中:
void preorder(struct TreeNode* root,int* arr,int* i)
{if(root==NULL){return;}//前序遍历的顺序:根、左子树、右子树arr[(*i)++]=root->val;preorder(root->left,arr,i); preorder(root->right,arr,i);
}
完整代码如下:
int TreeSize(struct TreeNode* root)
{if(root==NULL){return 0;}return TreeSize(root->left)+TreeSize(root->right)+1;
}
void preorder(struct TreeNode* root,int* arr,int* i)
{if(root==NULL){return;}arr[(*i)++]=root->val;preorder(root->left,arr,i); preorder(root->right,arr,i);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){*returnSize=0;int n=TreeSize(root);int* ret=(int*)malloc(sizeof(int)*n);preorder(root,ret,returnSize);return ret;
}
此外还有中序遍历、后序遍历、大家可以自行练习。
二叉树的中序遍历
二叉树的后序遍历
总结
本期主要的内容是学会二叉树的递归遍历,除此之外二叉树还有层序遍历,层序遍历需要的数据结构更复杂一点,下期我再向大家一一介绍,以上便是本前期全部内容,最后,感谢阅读!
相关文章:
数据结构刷题训练——二叉树篇(一)
📙作者简介: 清水加冰,目前大二在读,正在学习C/C、Python、操作系统、数据库等。 📘相关专栏:C语言初阶、C语言进阶、C语言刷题训练营、数据结构刷题训练营、有感兴趣的可以看一看。 欢迎点赞 👍…...
2023版 STM32实战5 基本定时器中断
基本定时器简介与特性 -1-时钟可分频 -2-计数模式只可以选择累加 -3-只可以用来定时(含中断) 查看时钟源 如图定时器7的时钟最大为72MHZ 定时时间的计算 通用定时器的时间计算公式为 Tout ((arr1)(psc1&…...
css3实现页面元素抖动效果
html <div id"shake" class"shape">horizontal shake</div>js(vue3) function shake(elemId) {const elem document.getElementById(elemId)console.log(获取el, elem)if (elem) {elem.classList.add(shake)setTimeou…...
[架构之路-232]:操作系统 - 文件系统存储方法汇总
目录 前言: 一、文件系统存储方法基本原理和常见应用案例: 二、Windows FAT文件系统 2.1 概述 三、Linux EXT文件系统 3.1 基本原理 3.2 索引节点表(Inode Table) 3.2.1 索引节点表层次结构 3.2.2 间接索引表的大小和表项…...
简述 AOP 动态代理
一、AopAutoConfiguration 源码: Configuration(proxyBeanMethods false) ConditionalOnProperty(prefix "spring.aop", name "auto", havingValue "true", matchIfMissing true) public class AopAutoConfiguration {Configur…...
机器学习基础之《分类算法(8)—随机森林》
一、什么是集成学习方法 1、定义 集成学习通过建立几个模型组合的来解决单一预测问题。它的工作原理是生成多个分类器/模型,各自独立地学习和作出预测。这些预测最后结合成组合预测,因此优于任何一个单分类的做出预测 谚语:三个臭皮匠顶个诸…...
Python数据攻略-Pandas进行CSV和Excel文件读写
在数据分析的世界里,能够读取和写入不同格式的文件是一项基本而重要的技能。CSV(逗号分隔值)和Excel是两种常见的数据存储格式。它们在商业、科研、教育等多个领域都有广泛应用。 文章目录 读取CSV文件`pd.read_csv()` 文件读取函数的基本用法`DataFrame.to_csv()` 数据写入…...
lv7 嵌入式开发-网络编程开发 13 UNIX域套接字
1 UNIX 域流式套接字 本地地址 struct sockaddr_un {unsigned short sun_family; /* 协议类型 */char sun_path[108]; /* 套接字文件路径 */ };UNIX 域流式套接字的用法和 TCP 套接字基本一致,区别在于使用的协议和地址不同 UNIX 域流式套接字服务器端…...
blender光照系统设置
0)Viewport Shading设置里面的Lighting下面的参数: Scene Lights,Scene World - Scene Lights是指在渲染模式下是否使用场景中的灯光对象来照亮物体。 - Scene World是指在渲染模式下是否使用场景中的世界设置来作为背景和环境光。如果关闭该选项&#…...
华为云云耀云服务器L实例评测|基于canal缓存自动更新流程 SpringBoot项目应用案例和源码
前言 最近华为云云耀云服务器L实例上新,也搞了一台来玩,期间遇到各种问题,在解决问题的过程中学到不少和运维相关的知识。 在之前的博客中,介绍过canal的安装和配置,参考博客 拉取创建canal镜像配置相关参数 & …...
vue3 中使用echarts图表——柱状图
柱状图是比较常用的图形结构,所以我先收集一些精美的柱状图 一、柱状图:设置圆角和颜色 <template><div class"box" ref"chartDom"></div> </template> <script setup> import { ref, onMounted } fr…...
基于Java的家政公司服务平台设计与实现(源码+lw+部署文档+讲解等)
文章目录 前言具体实现截图论文参考详细视频演示为什么选择我自己的网站自己的小程序(小蔡coding)有保障的售后福利 代码参考源码获取 前言 💗博主介绍:✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计划导师、全栈领域优质创作…...
深入了解 PostgreSQL:功能、特性和部署
PostgreSQL,通常简称为Postgres,是一款强大且开源的关系型数据库管理系统(RDBMS),它在数据存储和处理方面提供了广泛的功能和灵活性。本文将详细介绍 PostgreSQL 的功能、特性以及如何部署和使用它。 什么是 PostgreSQ…...
平台项目列表页实现(二)
这里写目录标题 一、顶部盒子设计1. 顶部盒子包含项目列表和添加项目、退出登录2个按钮 二、项目列表盒子设计三、添加项目盒子设计四、退出登录功能实现五、路由导航守卫实现六、展示项目信息七、bug修复1、当项目名称太长或者项目负责人太长,需要一行展示…...
osg实现鼠标框选
目录 1. 需求的提出 2. 具体实现 2.1. 禁止场景跟随鼠标转动 2.2. 矩形框前置绘制 3. 附加说明 3.1. 颜色设置说明 3.2.矩形框显示和隐藏的另一种实现 1. 需求的提出 有时需要在屏幕通过按住键盘上的某个键如Ctrl键且按住鼠标左键,拖出一个矩形,实现框…...
电路原理解题笔记(一)
文章目录 贼基础的知识等效电阻基尔霍夫电流定律电阻电路的一般分析支路电流法节点电压法回路电流法 电路定理叠加定理戴维宁等效电路诺顿等效电路求某电阻值为多少可吸收最大功率。吸收、释放功率 第一个月,对应猴博士的一到五课时。 贼基础的知识电阻电路的等效变…...
分享几个优秀开源免费管理后台模版,建议收藏!
大家好,我是 jonssonyan 今天和大家分享一些免费开源的后台管理页面,帮助大家快速搭建前端页面。为什么要用模板?道理很简单,原因是方便我们快速开发。我们不应该花太多的时间在页面调整上,而应该把精力放在核心逻辑和…...
BFS模板:844. 走迷宫
给定一个 nmnm 的二维整数数组,用来表示一个迷宫,数组中只包含 00 或 11,其中 00 表示可以走的路,11 表示不可通过的墙壁。 最初,有一个人位于左上角 (1,1)(1,1) 处,已知该人每次可以向上、下、左、右任意…...
re学习(37)DASCTF 2023 0X401七月暑期挑战赛 controflow
程序通过改变栈里面的返回地址来控制程序的控制流 从而达到混淆的效果 左侧有许多被hook的函数 在每个函数开头设置断点 然后观察程序的运行流程 会发现输入的数据会进行 异或 相加 异或 相减 相乘 异或等操作 要注意部分运算的索引是 从[10]开始的 具体思路参考…...
数字IC前端学习笔记:数字乘法器的优化设计(进位保留乘法器)
相关阅读 数字IC前端https://blog.csdn.net/weixin_45791458/category_12173698.html?spm1001.2014.3001.5482 阵列乘法器设计中限制乘法器速度的是随着数据位宽而迅速增大的串行进位链,如果使用进位保留加法器,则可以避免在设计中引入较长时间的等待&…...
prority_queue的学习
优先级队列(Priority Queue)是一种抽象数据类型,它类似于普通的队列或堆栈,但每个元素都有一个关联的优先级,这个优先级决定了元素在队列中的位置和被访问的顺序。在优先级队列中,具有最高优先级的元素通常…...
【vue3】toRef与toRefs的使用,toRef与ref的区别
假期第四篇,对于基础的知识点,我感觉自己还是很薄弱的。 趁着假期,再去复习一遍 1、toRef与toRefs 创建一个ref对象,其value值指向另一个对象中的某个属性 语法:const name toRef(person,‘name’…...
信息论基础第二章部分习题
2.5 证明若H(Y|X)0,则Y是X的函数 若 H ( Y ∣ X ) 0 H(Y|X) 0 H(Y∣X)0,意味着在已知 X X X 的条件下, Y Y Y 的不确定性为零,即给定 X X X 的值,我们完全确定了 Y Y Y 的值。这表明 Y Y Y 的取值完全由 X X…...
信息化发展73
数字经济 数字经济是继农业经济、工业经济之后的更高级经济形态。从本质上看,数字经济是一种新的技术经济范式,它建立在信息与通信技术的重大突破的基础上,以数字技术与实体经济融合驱动的产业梯次转型和经济创新发展的主引擎,在…...
560. 和为 K 的子数组
题目描述 给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的连续子数组的个数 。 示例 1: 输入:nums [1,1,1], k 2 输出:2示例 2: 输入:nums [1,2,3], k 3 输出:2…...
24 mysql all 查询
前言 这里主要是 探究一下 explain $sql 中各个 type 诸如 const, ref, range, index, all 的查询的影响, 以及一个初步的效率的判断 这里会调试源码来看一下 各个类型的查询 需要 lookUp 的记录 以及 相关的差异 此系列文章建议从 mysql const 查询 开始看 测试表结构…...
【Excel单元格数值统计】python实现-附ChatGPT解析
1.题目 Excel单元格数值统计 知识点: 递归、循环数组 时间限制:2s 空间限制:256MB 限定语言:不限 题目描述: Excel工作表中对选定区域的数值进行统计的功能非常实用。仿照Excel的这个功能,请对给定表格中选中区域中的单元格进行求和统计,并输出统计结果。 为简化计算,假设当…...
爬虫项目实战——爬取B站视频
目标:对B站视频详情页url进行视频的爬取。 注:由于B站的音频和视频的链接是分开的,所以在提取是需要分别提取,然后进行合成。 这里只管提取,合成的工作以后再说。 具体步骤 发送请求 对于视频详情页url地址发送请求 …...
关掉在vscode使用copilot时的提示音
1. 按照图示的操作File --> Preferences --> Settings 2. 搜索框输入关键字Sound,因为是要关掉声音,所以找有关声音的设置 3. 找到如下图所示的选项 Audio Cues:Line Has Inline Suggetion,将其设置为Off 这样,就可以关掉suggest code时…...
【有限域除法】二元多项式除法电路原理及C语言实现
二元多项式除法电路原理 例: g ( x ) = x 4 + x 2 + x + 1 g(x)=x^4 + x^2+x+1...
建设国家游戏网站/网站权重排名
今日任务做了什么明日任务李嘉良(18)写换皮肤功能研究相关技术开始着手编写代码王泓洋(29)优化metro图标商讨设计图标修改图标王熹(29)优化metro图标商讨设计图标修改图标王冬(32)修改设置按钮有事外出,请假完成设置按钮的修改刘明(30)单元测试学习单元测试相关知识尝试进行单元…...
北京 好的网站制作/最新黑帽seo教程
首先需要明确一点alloc_flags和gfp_mask之间的区别,gfp_mask是使用alloc_pages申请内存时所传递的申请标记,而alloc_flags是在内存管理子系统内部使用的另一个标记,二者是不同的,当然alloc_flags也是从gfp_mask经过计算得到的。 …...
做7寸照片的网站/搜索引擎提交入口网址
注意进位的处理和节点为null的处理 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {int flag 0;ListNode res null;ListNode temp null;//注意如果进位不是0的话还要添加一个节点while (l1!null||l2!null||flag!0){int cur flag;flag 0;if (l1!null) {curl1.v…...
建设部网站公示公告安全/太原seo关键词排名
webrtcWeb实时通信(WebRTC)旨在为开发人员提供使用简单JavaScript API创建高清视频和音频呼叫的能力。 这些API直接嵌入在浏览器中,不需要任何插件,下载或任何类型的安装即可启动并运行。 Google花费了大约2亿美元来开源该技术&a…...
网站建设应该注意哪些原则/目录型搜索引擎有哪些
也许可以通过更改获取数据的格式来简化这一过程,但下面的示例应该可以帮助您顺利完成任务。我完全跳过了zip方法,而用熊猫的方式来做这件事。为了测试,我创建了一个虚拟函数来返回一组固定产品的随机价格:import pandas as pddef …...
wordpress内插件翻译/上海seo外包
题目链接:https://vjudge.net/problem/UVA-10305 解题思路:单向建边,将终点的入度加一。 当一个点入度为0时,这个点就可以被输出,同时这个点对应所有终点入度减一。 用bfs实现。 代码: #include<cs…...