二叉树问题——前/中/后/层遍历问题(递归与栈)
摘要
博文主要介绍二叉树的前/中/后/层遍历(递归与栈)方法
一、前/中/后/层遍历问题
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 }} &…...
Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
OpenLayers 分屏对比(地图联动)
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能,和卷帘图层不一样的是,分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...
【笔记】WSL 中 Rust 安装与测试完整记录
#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统:Ubuntu 24.04 LTS (WSL2)架构:x86_64 (GNU/Linux)Rust 版本:rustc 1.87.0 (2025-05-09)Cargo 版本:cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...
Python Einops库:深度学习中的张量操作革命
Einops(爱因斯坦操作库)就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库,用类似自然语言的表达式替代了晦涩的API调用,彻底改变了深度学习工程…...
MySQL 部分重点知识篇
一、数据库对象 1. 主键 定义 :主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 :确保数据的完整性,便于数据的查询和管理。 示例 :在学生信息表中,学号可以作为主键ÿ…...
LangFlow技术架构分析
🔧 LangFlow 的可视化技术栈 前端节点编辑器 底层框架:基于 (一个现代化的 React 节点绘图库) 功能: 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...
SQL Server 触发器调用存储过程实现发送 HTTP 请求
文章目录 需求分析解决第 1 步:前置条件,启用 OLE 自动化方式 1:使用 SQL 实现启用 OLE 自动化方式 2:Sql Server 2005启动OLE自动化方式 3:Sql Server 2008启动OLE自动化第 2 步:创建存储过程第 3 步:创建触发器扩展 - 如何调试?第 1 步:登录 SQL Server 2008第 2 步…...
mac:大模型系列测试
0 MAC 前几天经过学生优惠以及国补17K入手了mac studio,然后这两天亲自测试其模型行运用能力如何,是否支持微调、推理速度等能力。下面进入正文。 1 mac 与 unsloth 按照下面的进行安装以及测试,是可以跑通文章里面的代码。训练速度也是很快的。 注意…...
