二叉树问题——前/中/后/层遍历问题(递归与栈)
摘要
博文主要介绍二叉树的前/中/后/层遍历(递归与栈)方法
一、前/中/后/层遍历问题
144. 二叉树的前序遍历
145. 二叉树的后序遍历
94. 二叉树的中序遍历
102. 二叉树的层序遍历
103. 二叉树的锯齿形层序遍历
二、二叉树遍历递归解析
// 前序遍历·递归·LC144_二叉树的前序遍历
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<Integer>();preorder(root, result);return result;}public void preorder(TreeNode root, List<Integer> result) {if (root == null) {return;}result.add(root.val);preorder(root.left, result);preorder(root.right, result);}
}// 中序遍历·递归·LC94_二叉树的中序遍历
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();inorder(root, res);return res;}void inorder(TreeNode root, List<Integer> list) {if (root == null) {return;}inorder(root.left, list);list.add(root.val); // 注意这一句inorder(root.right, list);}
}// 后序遍历·递归·LC145_二叉树的后序遍历
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();postorder(root, res);return res;}void postorder(TreeNode root, List<Integer> list) {if (root == null) {return;}postorder(root.left, list);postorder(root.right, list);list.add(root.val); // 注意这一句}
}
三、二叉树遍历栈解析



// 前序遍历顺序:中-左-右,入栈顺序:中-右-左
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null){return result;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()){TreeNode node = stack.pop();result.add(node.val);if (node.right != null){stack.push(node.right);}if (node.left != null){stack.push(node.left);}}return result;}
}// 中序遍历顺序: 左-中-右 入栈顺序: 左-右
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null){return result;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()){if (cur != null){stack.push(cur);cur = cur.left;}else{cur = stack.pop();result.add(cur.val);cur = cur.right;}}return result;}
}// 后序遍历顺序 左-右-中 入栈顺序:中-左-右 出栈顺序:中-右-左, 最后翻转结果
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null){return result;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()){TreeNode node = stack.pop();result.add(node.val);if (node.left != null){stack.push(node.left);}if (node.right != null){stack.push(node.right);}}Collections.reverse(result);return result;}
}
四、二叉树层序遍历解析

// 102.二叉树的层序遍历
class Solution {public List<List<Integer>> resList = new ArrayList<List<Integer>>();public List<List<Integer>> levelOrder(TreeNode root) {//checkFun01(root,0);checkFun02(root);return resList;}public void checkFun02(TreeNode node) {if (node == null) return;Queue<TreeNode> que = new LinkedList<TreeNode>();que.offer(node);while (!que.isEmpty()) {List<Integer> itemList = new ArrayList<Integer>();int len = que.size();while (len > 0) {TreeNode tmpNode = que.poll();itemList.add(tmpNode.val);if (tmpNode.left != null) que.offer(tmpNode.left);if (tmpNode.right != null) que.offer(tmpNode.right);len--;}resList.add(itemList);}}
}
博文参考
《leetcode》
相关文章:
二叉树问题——前/中/后/层遍历问题(递归与栈)
摘要 博文主要介绍二叉树的前/中/后/层遍历(递归与栈)方法 一、前/中/后/层遍历问题 144. 二叉树的前序遍历 145. 二叉树的后序遍历 94. 二叉树的中序遍历 102. 二叉树的层序遍历 103. 二叉树的锯齿形层序遍历 二、二叉树遍历递归解析 // 前序遍历递归LC144_二叉树的前…...
Vue3问题:如何实现级联菜单的数据懒加载?
前端功能问题系列文章,点击上方合集↑ 序言 大家好,我是大澈! 本文约3100字,整篇阅读大约需要5分钟。 本文主要内容分三部分,第一部分是需求分析,第二部分是实现步骤,第三部分是问题详解。 …...
STM32-电源管理(实现低功耗)
电源管理 STM32 HAL库对电源管理提供了完善的函数和命令。 工作模式(高功耗->低功耗):运行、睡眠、停止、待机。 若备份域电源正常供电,备份域内的RTC都可以正常运行,备份域内的寄存器的数据会被保存,不…...
vue 自己捣鼓周日程日历组件
需求:想要一个周日程表,记录每天的计划,点击可查看详情。可自定义时间段通过后台获取时间段显示 分析: 通过需求,超级课程表app这款软件其中课表和这个需求很像,只不过这个需求第一列的时间段是自定义的,不是上午下午两个,但是原理都差不多 原本想找一些第三方插件使…...
【力扣】2127. (分类讨论 + 拓扑排序)参加会议的最多员工数
【力扣】2127. (分类讨论 拓扑排序)参加会议的最多员工数 文章目录 【力扣】2127. (分类讨论 拓扑排序)参加会议的最多员工数1. 题目介绍2. 思路(**分类讨论 拓扑排序**)3. 解题代码4. Danger参考 1. 题…...
Flutter——最详细(Map)使用教程
Map简介 键值对的集合,您可以使用其关联的键从中检索值。 普通的 HashMap是无序的(不保证顺序),LinkedHashMap 按键插入顺序迭代,而像 SplayTreeMap 这样的排序映射按排序顺序迭代键。 1,添加元素 addEntri…...
vue的入门第一课
Vue.js是一款流行的JavaScript框架,用于构建交互式Web应用程序。本文将详细介绍Vue.js的基础知识,包括Vue.js的历史、设计模式、构造函数参数、el、data、computed、method、watch以及差值的使用。 Vue.js是什么? Vue.js是一款用于构建用户…...
已解决:conda找不到对应版本的cudnn如何解决?
1.解决方法 配置深度学习环境时,打算安装cudatoolkit11.2和cudnn8.1,当使用conda install cudnn8.0时,却搜索不到这个版本的包,解决方法如下: conda search cudnn -c conda-forge然后就可以使用如下命令进行安装对应…...
大语言模型的学习路线和开源模型的学习材料《二》
第三层 LLMs to Artifact 第一重 langchain 【LLMs 入门实战 —— 十二 】基于 本地知识库 的高效 🤖langchain-ChatGLM 介绍:langchain-ChatGLM是一个基于本地知识的问答机器人,使用者可以自由配置本地知识,用户问题的答案也是基于本地知识生成的。【LLMs 入门实战 ——…...
Flask-SQLAlchemy事件钩子介绍
一、前言 前几天在搜资料的时候无意中看到有介绍SQLAlchemy触发器,当时感觉挺奇怪的,触发器不是数据库层面的概念吗,怎么flask-SQLAlchemy这个ORM框架会有这玩意。 二、SQLAlchemy触发器一个简单例子 考虑到效率博客表中有两个字段…...
C++——list
目录 list介绍 list的函数接口 构造函数 push_front和pop_front push_back和pop_back insert erase 迭代器 front和back size resize empty clear list::sort unique reverse 迭代器的实现 list介绍 list是一种可以在常数范围内在任意位置进行插入和删除的序列…...
【Linux】第九站:make和makefile
文章目录 一、 Linux项目自动化构建工具make/Makefile1.make/makefile工作现象2.依赖关系与依赖方法3.如何清理4.为什么这里我们需要带上clean5.连续的make6.特殊符号 二、Linux下实现一个简单的进度条1.回车换行2.缓冲区3.倒计时的实现 一、 Linux项目自动化构建工具make/Make…...
一文了解什么是WebSocket
WebSocket 允许我们创建“实时”应用程序,与传统 API 协议相比,该应用程序速度更快且开销更少。 一、WebSocket 是如何工作的 按照传统的定义,WebSocket是一种双工协议,主要用于客户端-服务器通信通道。它本质上是双向的&…...
redis是什么
redis是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库,并提供多种语言的API。和Memcached类似。redis支持存储的value类型相对更多,包括string(字符串)、list(链表)、set(集合)和zset(有序集合)。 一、 基本…...
基于深度学习的人脸专注度检测计算系统 - opencv python cnn 计算机竞赛
文章目录 1 前言2 相关技术2.1CNN简介2.2 人脸识别算法2.3专注检测原理2.4 OpenCV 3 功能介绍3.1人脸录入功能3.2 人脸识别3.3 人脸专注度检测3.4 识别记录 4 最后 1 前言 🔥 优质竞赛项目系列,今天要分享的是 🚩 基于深度学习的人脸专注度…...
跨境电商的新引擎:崛起的网红经济
随着全球数字化时代的崛起,跨境电商成为了国际贸易的新引擎,而在这个巨大的变革浪潮中,网红经济正在崭露头角,成为这一引擎的有力推动者。在这篇文章中,我们将深入探讨网红经济如何催生跨境电商的新动力,以…...
P2006 赵神牛的游戏 python解法
赵神牛的游戏 题目描述 在 DNF 中,赵神牛有一个缔造者,他一共有 k k k 点法力值,一共有 m m m 个技能,每个技能耗费的法力值为 a i a_i ai,可以造成的伤害为 b i b_i bi,而 boss 的体力值为 n n…...
Unity的碰撞检测(六)
温馨提示:本文基于前一篇“Unity的碰撞检测(五)”继续探讨两个游戏对象具备刚体的BodyType均为Dynamic,但是Collision Detection属性不同的碰撞检测,阅读本文则默认已阅读前文。 (一)测试说明 在基于两个游戏对象都具…...
从前序与中序遍历序列构造二叉树
代码如下,开袋即食 class Solution {private Map<Integer,Integer> map;public TreeNode buildTree(int[] preorder, int[] inorder) {map new HashMap<>();for(int i 0;i<preorder.length;i){map.put(inorder[i],i);}return build(preorder,inord…...
antd5上传图片显示405解决
antd5上传图片,默认使用上传方式会调用本地的接口。 405 Method Not Allowed 状态码 405 Method Not Allowed 表明服务器禁止了使用当前 HTTP 方法的请求。 Upload {...props}beforeUpload{(file) > {//自定义上传图片的逻辑//最后返回falsereturn false }} &…...
AngularJS 控制器详解
AngularJS 控制器详解 引言 AngularJS 是一个用于构建动态网页的框架,它允许开发者使用 HTML 作为模板语言,通过指令扩展 HTML 的功能。在 AngularJS 中,控制器是核心组件之一,它负责管理视图和模型之间的交互。本文将详细介绍 AngularJS 控制器的概念、作用、创建方法以…...
JMeter深度实战:从HTTP接口测试到性能根因分析
1. 这不是“点点按钮就能出报告”的玩具,而是接口质量的显微镜很多人第一次打开JMeter,以为它就是个带图形界面的curl增强版——填个URL、点下“启动”,等几秒看个响应码,再导出个Excel就完事了。我刚接手电商中台接口测试时也这么…...
ChatGPT绘画提示词生成效率革命(92%设计师不知道的5层语义嵌套法)
更多请点击: https://kaifayun.com 第一章:ChatGPT绘画提示词生成效率革命(92%设计师不知道的5层语义嵌套法) 传统提示词工程常陷于“关键词堆砌”误区,而真正高阶的生成控制源于语义结构的纵深组织。5层语义嵌套法将…...
FAIR原则下的多元时间序列异常检测:科学数据挑战与实战策略
1. 项目概述:当科学前沿遇上FAIR数据挑战在数据驱动的科学发现时代,我们常常面临一个核心矛盾:一方面,我们有能力采集前所未有的海量、高维数据;另一方面,从这些数据“海洋”中精准捞出那几颗代表新现象、新…...
别再只会用cp了!用dd命令给硬盘做‘全身体检’和‘克隆手术’(附实战命令)
别再只会用cp了!用dd命令给硬盘做‘全身体检’和‘克隆手术’(附实战命令)在Linux系统管理中,文件复制是最基础的操作之一。大多数用户习惯使用cp命令完成日常的文件复制任务,但当面对磁盘级操作时,cp就显得…...
亚太赫兹ISAC技术:机器联觉与多模态融合的6G通信
1. 亚太赫兹ISAC技术概述在6G通信系统中,集成感知与通信(ISAC)技术正成为支撑智能交通、低空经济等新兴应用的核心基础设施。亚太赫兹频段(100-300GHz)因其超大带宽特性,能够同时实现100Gbps级通信速率和亚毫米级感知精度,成为ISAC系统的理想…...
从塔防到RPG:在Unity里用A*算法实现不同游戏类型的敌人AI(实战案例)
从塔防到RPG:在Unity里用A*算法实现不同游戏类型的敌人AI(实战案例)当你在玩一款塔防游戏时,是否好奇那些怪物为何总能找到通往终点的最优路径?或者在RPG游戏中,NPC为何能绕过复杂地形精准追踪玩家…...
AArch64缓存架构解析与性能优化实践
1. AArch64缓存架构基础解析AArch64架构作为ARMv8指令集的64位执行状态,其缓存系统设计体现了现代处理器架构的典型特征。缓存作为CPU与主存之间的高速缓冲存储器,通过存储频繁访问的数据和指令来减少内存访问延迟。在AArch64中,缓存被组织为…...
丈母娘只要第一眼看不上女婿,即使后面结婚了,大概率也会一直看不上,大家觉得对吗?——为什么有些丈母娘总是挑女婿的不是,没事就发货大吼?——
很多家庭里,确实存在这种现象,但“第一眼看不上=一辈子看不上”,并不是绝对规律。 丈母娘对女婿的第一印象往往很强,因为她看的不是单纯“喜不喜欢”,而是: 这个男人靠不靠谱 能不能让女儿过得稳定 性格是否成熟 家庭背景、经济能力、处事方式是否安心 对女儿有没有…...
P1313 计算系数【洛谷算法习题】
P1313 计算系数 网页链接 P1313 计算系数 题目描述 给定一个多项式 (byax)k(byax)^k(byax)k,请求出多项式展开后 xnymx^n\times y^mxnym 项的系数。 输入格式 输入共一行,包含 555 个整数,分别为 a,b,k,n,ma,b,k,n,ma,b,k,n,m…...
