当前位置: 首页 > news >正文

数据结构刷题训练——二叉树篇(一)

📙作者简介: 清水加冰,目前大二在读,正在学习C/C++、Python、操作系统、数据库等。

📘相关专栏:C语言初阶、C语言进阶、C语言刷题训练营、数据结构刷题训练营、有感兴趣的可以看一看。

欢迎点赞 👍 收藏 ⭐留言 📝 如有错误还望各路大佬指正!

✨每一次努力都是一种收获,每一次坚持都是一种成长✨       

在这里插入图片描述

目录

 前言

📖题目1:翻转二叉树

📖题目2:相同的树

📖题目3:对称二叉树

📖题目4:另一棵树的子树

 📖题目5:二叉树的前序遍历

总结


 前言

        我们学习了二叉树的顺序结构和链式结构,在日常刷题在,我们最常见的就是链式二叉树,刚学习完链式二叉树刷题上手比较难,本期我将继续开始数据结构刷题专栏,为大家提供二叉树(初阶)相关的练习和力扣OJ的经典题目以及题目讲解,以便于大家更容易上手二叉树部分的刷题。


📖题目1:翻转二叉树

题目描述:

题目链接:

翻转二叉树icon-default.png?t=N7T8https://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:相同的树

题目描述:

 

 题目链接:

相同的树icon-default.png?t=N7T8https://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:对称二叉树

题目描述:

 

 题目链接:

对称二叉树icon-default.png?t=N7T8https://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:另一棵树的子树

 

 题目链接:

另一棵树的子树icon-default.png?t=N7T8https://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:二叉树的前序遍历

 题目描述:

 

题目链接:

二叉树的前序遍历icon-default.png?t=N7T8https://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语言刷题训练营、数据结构刷题训练营、有感兴趣的可以看一看。 欢迎点赞 &#x1f44d…...

2023版 STM32实战5 基本定时器中断

基本定时器简介与特性 -1-时钟可分频 -2-计数模式只可以选择累加 -3-只可以用来定时(含中断) 查看时钟源 如图定时器7的时钟最大为72MHZ 定时时间的计算 通用定时器的时间计算公式为 Tout ((arr1)(psc1&…...

css3实现页面元素抖动效果

html <div id"shake" class"shape">horizontal shake</div>js&#xff08;vue3&#xff09; function shake(elemId) {const elem document.getElementById(elemId)console.log(获取el, elem)if (elem) {elem.classList.add(shake)setTimeou…...

[架构之路-232]:操作系统 - 文件系统存储方法汇总

目录 前言&#xff1a; 一、文件系统存储方法基本原理和常见应用案例&#xff1a; 二、Windows FAT文件系统 2.1 概述 三、Linux EXT文件系统 3.1 基本原理 3.2 索引节点表&#xff08;Inode Table&#xff09; 3.2.1 索引节点表层次结构 3.2.2 间接索引表的大小和表项…...

简述 AOP 动态代理

一、AopAutoConfiguration 源码&#xff1a; Configuration(proxyBeanMethods false) ConditionalOnProperty(prefix "spring.aop", name "auto", havingValue "true", matchIfMissing true) public class AopAutoConfiguration {Configur…...

机器学习基础之《分类算法(8)—随机森林》

一、什么是集成学习方法 1、定义 集成学习通过建立几个模型组合的来解决单一预测问题。它的工作原理是生成多个分类器/模型&#xff0c;各自独立地学习和作出预测。这些预测最后结合成组合预测&#xff0c;因此优于任何一个单分类的做出预测 谚语&#xff1a;三个臭皮匠顶个诸…...

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 套接字基本一致&#xff0c;区别在于使用的协议和地址不同 UNIX 域流式套接字服务器端…...

blender光照系统设置

0&#xff09;Viewport Shading设置里面的Lighting下面的参数&#xff1a; Scene Lights,Scene World - Scene Lights是指在渲染模式下是否使用场景中的灯光对象来照亮物体。 - Scene World是指在渲染模式下是否使用场景中的世界设置来作为背景和环境光。如果关闭该选项&#…...

华为云云耀云服务器L实例评测|基于canal缓存自动更新流程 SpringBoot项目应用案例和源码

前言 最近华为云云耀云服务器L实例上新&#xff0c;也搞了一台来玩&#xff0c;期间遇到各种问题&#xff0c;在解决问题的过程中学到不少和运维相关的知识。 在之前的博客中&#xff0c;介绍过canal的安装和配置&#xff0c;参考博客 拉取创建canal镜像配置相关参数 & …...

vue3 中使用echarts图表——柱状图

柱状图是比较常用的图形结构&#xff0c;所以我先收集一些精美的柱状图 一、柱状图&#xff1a;设置圆角和颜色 <template><div class"box" ref"chartDom"></div> </template> <script setup> import { ref, onMounted } fr…...

基于Java的家政公司服务平台设计与实现(源码+lw+部署文档+讲解等)

文章目录 前言具体实现截图论文参考详细视频演示为什么选择我自己的网站自己的小程序&#xff08;小蔡coding&#xff09;有保障的售后福利 代码参考源码获取 前言 &#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计划导师、全栈领域优质创作…...

深入了解 PostgreSQL:功能、特性和部署

PostgreSQL&#xff0c;通常简称为Postgres&#xff0c;是一款强大且开源的关系型数据库管理系统&#xff08;RDBMS&#xff09;&#xff0c;它在数据存储和处理方面提供了广泛的功能和灵活性。本文将详细介绍 PostgreSQL 的功能、特性以及如何部署和使用它。 什么是 PostgreSQ…...

平台项目列表页实现(二)

这里写目录标题 一、顶部盒子设计1. 顶部盒子包含项目列表和添加项目、退出登录2个按钮 二、项目列表盒子设计三、添加项目盒子设计四、退出登录功能实现五、路由导航守卫实现六、展示项目信息七、bug修复1、当项目名称太长或者项目负责人太长&#xff0c;需要一行展示&#xf…...

osg实现鼠标框选

目录 1. 需求的提出 2. 具体实现 2.1. 禁止场景跟随鼠标转动 2.2. 矩形框前置绘制 3. 附加说明 3.1. 颜色设置说明 3.2.矩形框显示和隐藏的另一种实现 1. 需求的提出 有时需要在屏幕通过按住键盘上的某个键如Ctrl键且按住鼠标左键&#xff0c;拖出一个矩形&#xff0c;实现框…...

电路原理解题笔记(一)

文章目录 贼基础的知识等效电阻基尔霍夫电流定律电阻电路的一般分析支路电流法节点电压法回路电流法 电路定理叠加定理戴维宁等效电路诺顿等效电路求某电阻值为多少可吸收最大功率。吸收、释放功率 第一个月&#xff0c;对应猴博士的一到五课时。 贼基础的知识电阻电路的等效变…...

分享几个优秀开源免费管理后台模版,建议收藏!

大家好&#xff0c;我是 jonssonyan 今天和大家分享一些免费开源的后台管理页面&#xff0c;帮助大家快速搭建前端页面。为什么要用模板&#xff1f;道理很简单&#xff0c;原因是方便我们快速开发。我们不应该花太多的时间在页面调整上&#xff0c;而应该把精力放在核心逻辑和…...

BFS模板:844. 走迷宫

给定一个 nmnm 的二维整数数组&#xff0c;用来表示一个迷宫&#xff0c;数组中只包含 00 或 11&#xff0c;其中 00 表示可以走的路&#xff0c;11 表示不可通过的墙壁。 最初&#xff0c;有一个人位于左上角 (1,1)(1,1) 处&#xff0c;已知该人每次可以向上、下、左、右任意…...

re学习(37)DASCTF 2023 0X401七月暑期挑战赛 controflow

程序通过改变栈里面的返回地址来控制程序的控制流 从而达到混淆的效果 左侧有许多被hook的函数 在每个函数开头设置断点 然后观察程序的运行流程 会发现输入的数据会进行 异或 相加 异或 相减 相乘 异或等操作 要注意部分运算的索引是 从[10]开始的 具体思路参考&#xf…...

数字IC前端学习笔记:数字乘法器的优化设计(进位保留乘法器)

相关阅读 数字IC前端https://blog.csdn.net/weixin_45791458/category_12173698.html?spm1001.2014.3001.5482 阵列乘法器设计中限制乘法器速度的是随着数据位宽而迅速增大的串行进位链&#xff0c;如果使用进位保留加法器&#xff0c;则可以避免在设计中引入较长时间的等待&…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

华为OD机考-机房布局

import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...

Razor编程中@Html的方法使用大全

文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...