每日一练:LeeCode-144、145、94.二叉树的前中后序遍历【二叉树】

news/2024/2/23 16:08:30/文章来源:https://blog.csdn.net/kdzandlbj/article/details/135613632

本文是力扣LeeCode-144、145、94.二叉树的前中后序遍历 学习与理解过程,本文仅做学习之用,对本题感兴趣的小伙伴可以出门左拐LeeCode前序遍历、中序遍历、后序遍历。

给你二叉树的根节点 root ,返回它节点值的 前序遍历

给定一个二叉树的根节点 root ,返回 它的 中序遍历

给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历

题目以前序遍历为例
示例 1:

在这里插入图片描述

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

示例 2:

输入:root = []
输出:[]

示例 3:

输入:root = [1]
输出:[1]

示例 4:
在这里插入图片描述

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

示例 5:
在这里插入图片描述

输入:root = [1,null,2]
输出:[1,2]

提示:

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

思路

递归法、迭代遍历法

1、递归法

1)确定递归函数的参数和返回值
2)确定终⽌条件
3)确定单层递归的逻辑

代码实现

前序遍历(中左右)

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();preOrder(root,res);return res;}public void preOrder(TreeNode root,List<Integer> res){	//确定递归函数的参数和返回值if(root==null)return;	//确定终⽌条件//确定单层递归的逻辑res.add(root.val);preOrder(root.left,res);preOrder(root.right,res);}
}

中序遍历(左中右)

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();preOrder(root,res);return res;}public void preOrder(TreeNode root,List<Integer> res){	//确定递归函数的参数和返回值if(root==null)return;	//确定终⽌条件//确定单层递归的逻辑preOrder(root.left,res);res.add(root.val);preOrder(root.right,res);}
}

后序遍历(左右中):

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();preOrder(root,res);return res;}public void preOrder(TreeNode root,List<Integer> res){	//确定递归函数的参数和返回值if(root==null)return;	//确定终⽌条件//确定单层递归的逻辑preOrder(root.left,res);preOrder(root.right,res);res.add(root.val);}
}

2、迭代遍历法

递归其实也是使用栈这种数据结构,只是不是显式地调用,迭代遍历法,就是用到实现
前序遍历(中左右)
由于的特性,我们需要先将根节点入栈,遍历完后,然后将右孩子入栈,再将左孩子入栈,因为这样才能保证遍历顺序是中左右

class Solution {public List<Integer> preorderTraversal(TreeNode root) {Stack<TreeNode> stack = new Stack<>();List<Integer> res = new ArrayList<>();if(root == null)return res;stack.push(root);while(!stack.isEmpty()){TreeNode node = stack.pop();	// 中res.add(node.val);if(node.right!=null)stack.push(node.right);	// 右(空节点不⼊栈)if(node.left!=null)stack.push(node.left);	// 左(空节点不⼊栈)}return res;}
}

前序遍历迭代遍历后,可以轻易带出后序遍历
后序遍历(左右中)
后序遍历的遍历顺序为:左右中前序遍历中左右,可以先将根节点入栈,遍历完后,然后将右左孩子入栈,再将右孩子入栈,最后将结果反转数组即可。

代码实现

class Solution {public List<Integer> postorderTraversal(TreeNode root) {Stack<TreeNode> stack = new Stack<>();List<Integer> res = new ArrayList<>();if(root == null)return res;stack.push(root);while(!stack.isEmpty()){TreeNode node = stack.pop();res.add(node.val);if(node.left!=null)stack.push(node.left);	//先将左孩子入栈if(node.right!=null)stack.push(node.right);	//再将右孩子入栈,以保证反转后的顺序}Collections.reverse(res);	//结果反转return res;}
}

中序遍历(左中右)

由于中序遍历遍历访问顺序(从根节点到叶子结点,从上往下)左中右处理顺序不一样前序和后序是一致的,所以,我们需要先使用指针,从最左边的叶子结点开始处理利用栈的出栈顺序,一个一个往根节点上走然后处理到根节点后,再处理根节点的右孩子

class Solution {public List<Integer> inorderTraversal(TreeNode root) {Stack<TreeNode> stack = new  Stack<>();List<Integer> res = new ArrayList<>();TreeNode cur = root;while(cur!=null || !stack.isEmpty()){if(cur!=null){	 // 指针来访问节点,访问到最底层stack.push(cur);	// 将访问的节点放进栈cur = cur.left;		// 左}else{cur = stack.pop();	 // 从栈⾥弹出的数据,就是要处理的数据(放进result数组⾥的数据)res.add(cur.val);	// 中cur = cur.right;	// 右}}return res;}
}

最重要的一句话:做二叉树的题目,首先需要确认的是遍历顺序
大佬们有更好的方法,请不吝赐教,谢谢

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

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

相关文章

scrapy爬虫实战

scrapy爬虫实战 Scrapy 简介主要特性示例代码 安装scrapy&#xff0c;并创建项目运行单个脚本代码示例配置itemsetting 爬虫脚本 代码解析xpath基本语法&#xff1a;路径表达式示例&#xff1a;通配符和多路径&#xff1a;函数&#xff1a;示例&#xff1a; 批量运行附录1&…

从“精益思想“看机器人的开发与应用:一场科技与效率的完美融合

在科技飞速发展的今天&#xff0c;机器人已经深入到我们的生活和工作之中&#xff0c;成为了提高效率、提升质量的重要工具。然而&#xff0c;如何让机器人的开发和利用更有效率、更精细&#xff0c;这是摆在我们面前的一道难题。此时&#xff0c;"精益思想"的出现&a…

OpenCV C++ 图像处理实战 ——《多尺度自适应Gamma矫正的低照图像增强》

OpenCV C++ 图像处理实战 ——《多尺度自适应Gamma矫正的低照图像增强》 一、结果演示二、多尺度自适应Gamma矫正的低照度图像增强2.1HSI颜色空间2.1.1 功能源码2.2 自适应于直方图分布的 Gamma 矫正2.2.1 功能源码2.3 多尺度 Retinex 分解与明度增强2.3.1 功能源码三、源码测试…

统计学-R语言-3

文章目录 前言给直方图增加正态曲线的不恰当之处直方图与条形图的区别核密度图时间序列图洛伦茨曲线计算绘制洛伦茨曲线所需的各百分比数值绘制洛伦茨曲线 练习 前言 本篇文章是介绍对数据的部分图形可视化的图型展现。 给直方图增加正态曲线的不恰当之处 需要注意的是&#…

【生存技能】git操作

先下载git https://git-scm.com/downloads 我这里是win64&#xff0c;下载了相应的直接安装版本 64-bit Git for Windows Setup 打开git bash 设置用户名和邮箱 查看设置的配置信息 获取本地仓库 在git bash或powershell执行git init&#xff0c;初始化当前目录成为git仓库…

力扣labuladong一刷day61天动态规划最小下降路径

力扣labuladong一刷day61天动态规划最优子结构 一、931. 下降路径最小和 题目链接&#xff1a;https://leetcode.cn/problems/minimum-falling-path-sum/description/ 如下图所示&#xff0c;求最小下降路径&#xff0c;定义dp[i][j]表示从最上面那行的任意位置抵达到nums[i]…

Redis分布式锁--java实现

文章目录 Redis分布式锁方案&#xff1a;SETNX EXPIRE基本原理比较好的实现会产生四个问题 几种解决原子性的方案方案&#xff1a;SETNX value值是&#xff08;系统时间过期时间&#xff09;方案&#xff1a;使用Lua脚本(包含SETNX EXPIRE两条指令)方案&#xff1a;SET的扩展…

springcloud Alibaba中gateway和sentinel联合使用

看到这个文章相信你有一定的sentinel和gateway基础了吧。 官网的gateway和sentinel联合使用有些过时了&#xff0c;于是有了这个哈哈&#xff0c;给你看看官网的&#xff1a; 才sentinel1.6&#xff0c;现在都几了啊&#xff0c;所以有些过时。 下面开始讲解&#xff1a; 首先…

【Linux】自定义shell

👑作者主页:@安 度 因 🏠学习社区:安度因 📖专栏链接:Linux 文章目录 获取命令行前置字段命令行输入解析命令行普通指令的执行子进程执行命令指令类型判断 && 内建命令总结 &&a

【Maven】007-Maven 工程的继承和聚合关系

【Maven】007-Maven 工程的继承和聚合关系 文章目录 【Maven】007-Maven 工程的继承和聚合关系一、Maven 工程的继承关系1、继承的概念2、继承的作用3、继承的语法4、父工程统一管理依赖版本父工程声明依赖版本子工程继承以来版本 二、Maven 工程的聚合关系1、聚合的概念2、聚合…

VitePress-01-从零开始的项目创建(npm版)

说明 本文介绍一下 VitePress的项目创建的步骤。 主要用到的命令工具是 npm。 本文的操作步骤是从无到有的创建一个完整的基本的【VitePress】项目。 环境准备 根据官方文档的介绍&#xff0c;截止本文发稿时&#xff0c;需要使用node.js 18 的版本。 可以使用node -v 的命令查…

【MySQL】MySQL表的约束-空属性/默认值/列属性/zerofill/主键/自增长/唯一键/外键

文章目录 表的约束1.空属性 --null && not null2.默认值 -- default3.列描述4.zerofill5.主键6.自增长7.唯一键8.外键 表的约束 表的约束&#xff1a;表中一定要有各种约束&#xff0c;通过约束&#xff0c;让我们未来插入数据库表中的数据是符合预期的。约束的本质是…

【GCC】6 接收端实现:周期构造RTCP反馈包

基于m98代码。GCC涉及的代码,可能位于:webrtc/modules/remote_bitrate_estimator webrtc/modules/congestion_controller webrtc/modules/rtp_rtcp/source/rtcp_packet/transport_feedback.cc webrtc 之 RemoteEstimatorProxy 对 remote_bitrate_estimator 的 RemoteEstimato…

Spark与HBase的集成与数据访问

Apache Spark和Apache HBase分别是大数据处理和分布式NoSQL数据库领域的两个重要工具。在本文中&#xff0c;将深入探讨如何在Spark中集成HBase&#xff0c;并演示如何通过Spark访问和操作HBase中的数据。将提供丰富的示例代码&#xff0c;以便更好地理解这一集成过程。 Spark…

【EI会议征稿通知】第四届图像处理与智能控制国际学术会议(IPIC 2024)

第四届图像处理与智能控制国际学术会议&#xff08;IPIC 2024&#xff09; 2024 4th International Conference on Image Processing and Intelligent Control 2024年第四届图像处理与智能控制国际学术会议&#xff08;IPIC 2024&#xff09;将于2024年5月3日-5日在吉隆坡举…

【Jmeter之get请求传递的值为JSON体实践】

Jmeter之get请求传递的值为JSON体实践 get请求的常见传参方式 1、在URL地址后面拼接&#xff0c;有多个key和value时&#xff0c;用&链接 2、在Parameters里面加上key和value 第一次遇到value的值不是字符串也不是整型&#xff0c;我尝试把json放到value里面&#xff0…

C练习——杨辉三角

题目&#xff1a; 打印近似杨辉三角&#xff0c;行数n自选 百度找的杨辉三角&#xff0c;参考一下&#xff1a; 解析&#xff1a; 把它的全部元素左对齐&#xff0c;就可以看成近似杨辉三角的样子 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 …… 每个数等于它上方两数…

OpenCV C++ 环境搭建和简单示例

OpenCV介绍 OpenCV&#xff1a;开源发行的跨平台计算机视觉和机器学习软件库&#xff0c;用C语言编写&#xff0c;提供了C &#xff0c;Python&#xff0c;Java和MATLAB接口&#xff0c;并支持Windows&#xff0c;Linux&#xff0c;Android和Mac OS。 OpenCV下载 去官网http…

常见面试题之CSS

CSS3的新特性 新增选择器&#xff1a;:nth-child()、:first-of-type、:last-of-type等 弹性盒子&#xff1a;display: flex 媒体查询&#xff1a;media根据设备的特性和屏幕大小应用不同的样式规则 多列布局&#xff1a;column-count和column-with等属性可以实现将内容分为多…

蓝桥杯每日一题----货物摆放

题目 分析 上来一看&#xff0c;三个for循环&#xff0c;从1到n&#xff0c;寻找满足lwhn的个数&#xff0c;但是这样根本跑不出来答案&#xff0c;n太大了&#xff0c;1e15的级别&#xff0c;O&#xff08;n&#xff09;的时间复杂度都不行&#xff0c;更何况是O&#xff08;…