数据结构刷题训练——二叉树篇(一)
📙作者简介: 清水加冰,目前大二在读,正在学习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 阵列乘法器设计中限制乘法器速度的是随着数据位宽而迅速增大的串行进位链,如果使用进位保留加法器,则可以避免在设计中引入较长时间的等待&…...

Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...

css实现圆环展示百分比,根据值动态展示所占比例
代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:
一、属性动画概述NETX 作用:实现组件通用属性的渐变过渡效果,提升用户体验。支持属性:width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项: 布局类属性(如宽高)变化时&#…...

CentOS下的分布式内存计算Spark环境部署
一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架,相比 MapReduce 具有以下核心优势: 内存计算:数据可常驻内存,迭代计算性能提升 10-100 倍(文档段落:3-79…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...

如何在网页里填写 PDF 表格?
有时候,你可能希望用户能在你的网站上填写 PDF 表单。然而,这件事并不简单,因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件,但原生并不支持编辑或填写它们。更糟的是,如果你想收集表单数据ÿ…...
docker 部署发现spring.profiles.active 问题
报错: org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...
rnn判断string中第一次出现a的下标
# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...
智能AI电话机器人系统的识别能力现状与发展水平
一、引言 随着人工智能技术的飞速发展,AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术,在客户服务、营销推广、信息查询等领域发挥着越来越重要…...