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

二叉树问题——前/中/后/层遍历问题(递归与栈)

摘要

博文主要介绍二叉树的前/中/后/层遍历(递归与栈)方法

一、前/中/后/层遍历问题

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问题:如何实现级联菜单的数据懒加载?

前端功能问题系列文章&#xff0c;点击上方合集↑ 序言 大家好&#xff0c;我是大澈&#xff01; 本文约3100字&#xff0c;整篇阅读大约需要5分钟。 本文主要内容分三部分&#xff0c;第一部分是需求分析&#xff0c;第二部分是实现步骤&#xff0c;第三部分是问题详解。 …...

STM32-电源管理(实现低功耗)

电源管理 STM32 HAL库对电源管理提供了完善的函数和命令。 工作模式&#xff08;高功耗->低功耗&#xff09;&#xff1a;运行、睡眠、停止、待机。 若备份域电源正常供电&#xff0c;备份域内的RTC都可以正常运行&#xff0c;备份域内的寄存器的数据会被保存&#xff0c;不…...

vue 自己捣鼓周日程日历组件

需求:想要一个周日程表,记录每天的计划,点击可查看详情。可自定义时间段通过后台获取时间段显示 分析: 通过需求,超级课程表app这款软件其中课表和这个需求很像,只不过这个需求第一列的时间段是自定义的,不是上午下午两个,但是原理都差不多 原本想找一些第三方插件使…...

【力扣】2127. (分类讨论 + 拓扑排序)参加会议的最多员工数

【力扣】2127. &#xff08;分类讨论 拓扑排序&#xff09;参加会议的最多员工数 文章目录 【力扣】2127. &#xff08;分类讨论 拓扑排序&#xff09;参加会议的最多员工数1. 题目介绍2. 思路&#xff08;**分类讨论 拓扑排序**&#xff09;3. 解题代码4. Danger参考 1. 题…...

Flutter——最详细(Map)使用教程

Map简介 键值对的集合&#xff0c;您可以使用其关联的键从中检索值。 普通的 HashMap是无序的&#xff08;不保证顺序&#xff09;&#xff0c;LinkedHashMap 按键插入顺序迭代&#xff0c;而像 SplayTreeMap 这样的排序映射按排序顺序迭代键。 1&#xff0c;添加元素 addEntri…...

vue的入门第一课

Vue.js是一款流行的JavaScript框架&#xff0c;用于构建交互式Web应用程序。本文将详细介绍Vue.js的基础知识&#xff0c;包括Vue.js的历史、设计模式、构造函数参数、el、data、computed、method、watch以及差值的使用。 Vue.js是什么&#xff1f; Vue.js是一款用于构建用户…...

已解决:conda找不到对应版本的cudnn如何解决?

1.解决方法 配置深度学习环境时&#xff0c;打算安装cudatoolkit11.2和cudnn8.1&#xff0c;当使用conda install cudnn8.0时&#xff0c;却搜索不到这个版本的包&#xff0c;解决方法如下&#xff1a; conda search cudnn -c conda-forge然后就可以使用如下命令进行安装对应…...

大语言模型的学习路线和开源模型的学习材料《二》

第三层 LLMs to Artifact 第一重 langchain 【LLMs 入门实战 —— 十二 】基于 本地知识库 的高效 🤖langchain-ChatGLM 介绍:langchain-ChatGLM是一个基于本地知识的问答机器人,使用者可以自由配置本地知识,用户问题的答案也是基于本地知识生成的。【LLMs 入门实战 ——…...

Flask-SQLAlchemy事件钩子介绍

一、前言 前几天在搜资料的时候无意中看到有介绍SQLAlchemy触发器&#xff0c;当时感觉挺奇怪的&#xff0c;触发器不是数据库层面的概念吗&#xff0c;怎么flask-SQLAlchemy这个ORM框架会有这玩意。 二、SQLAlchemy触发器一个简单例子 考虑到效率博客表中有两个字段&#xf…...

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 允许我们创建“实时”应用程序&#xff0c;与传统 API 协议相比&#xff0c;该应用程序速度更快且开销更少。​ 一、WebSocket 是如何工作的 按照传统的定义&#xff0c;WebSocket是一种双工协议&#xff0c;主要用于客户端-服务器通信通道。它本质上是双向的&…...

redis是什么

redis是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库&#xff0c;并提供多种语言的API。和Memcached类似。redis支持存储的value类型相对更多&#xff0c;包括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 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; 基于深度学习的人脸专注度…...

跨境电商的新引擎:崛起的网红经济

随着全球数字化时代的崛起&#xff0c;跨境电商成为了国际贸易的新引擎&#xff0c;而在这个巨大的变革浪潮中&#xff0c;网红经济正在崭露头角&#xff0c;成为这一引擎的有力推动者。在这篇文章中&#xff0c;我们将深入探讨网红经济如何催生跨境电商的新动力&#xff0c;以…...

P2006 赵神牛的游戏 python解法

赵神牛的游戏 题目描述 在 DNF 中&#xff0c;赵神牛有一个缔造者&#xff0c;他一共有 k k k 点法力值&#xff0c;一共有 m m m 个技能&#xff0c;每个技能耗费的法力值为 a i a_i ai​&#xff0c;可以造成的伤害为 b i b_i bi​&#xff0c;而 boss 的体力值为 n n…...

Unity的碰撞检测(六)

温馨提示&#xff1a;本文基于前一篇“Unity的碰撞检测(五)”继续探讨两个游戏对象具备刚体的BodyType均为Dynamic&#xff0c;但是Collision Detection属性不同的碰撞检测&#xff0c;阅读本文则默认已阅读前文。 &#xff08;一&#xff09;测试说明 在基于两个游戏对象都具…...

从前序与中序遍历序列构造二叉树

代码如下&#xff0c;开袋即食 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上传图片&#xff0c;默认使用上传方式会调用本地的接口。 405 Method Not Allowed 状态码 405 Method Not Allowed 表明服务器禁止了使用当前 HTTP 方法的请求。 Upload {...props}beforeUpload{(file) > {//自定义上传图片的逻辑//最后返回falsereturn false }} &…...

Spiderbuf_H05时间戳机制深度解析:锚点偏移与服务端校验

1. 这不是“破解”&#xff0c;是时间戳反爬机制的逆向解构你打开浏览器按F12&#xff0c;切到Network面板&#xff0c;刷新页面&#xff0c;盯着XHR请求发呆——那个带一长串数字的timestamp参数&#xff0c;每次刷新都变&#xff0c;但又不是随机乱跳&#xff0c;而是和当前时…...

如何快速搭建Windows虚拟路由器:VirtualRouter完整使用指南

如何快速搭建Windows虚拟路由器&#xff1a;VirtualRouter完整使用指南 【免费下载链接】VirtualRouter Wifi Hotspot for Windows computers (Windows 7, 8.x, Server 2012 and newer!) 项目地址: https://gitcode.com/gh_mirrors/vi/VirtualRouter VirtualRouter是一款…...

量子机器学习对称性工程权衡:Twirlator工具解析与实战指南

1. 量子机器学习中的对称性&#xff1a;从理论到工程实践的权衡在量子机器学习&#xff08;QML&#xff09;领域&#xff0c;我们一直在寻找能够提升模型性能、加速训练并增强泛化能力的“银弹”。对称性&#xff0c;这个在经典几何深度学习&#xff08;Geometric Deep Learnin…...

ARM SVE2 STNT1H指令:非临时存储优化技术详解

1. ARM SVE指令集与STNT1H指令概述在现代处理器架构中&#xff0c;向量处理技术已经成为提升计算性能的关键手段。作为ARMv9架构的重要组成部分&#xff0c;可扩展向量扩展(Scalable Vector Extension, SVE)指令集通过引入可变长度的向量寄存器&#xff0c;为高性能计算应用提供…...

ABAP 关键用户版本语句白名单全解析:从语法限制到实战案例

在很多 SAP S/4HANA Cloud 项目里,业务关键用户已经不再满足于只提需求、等 IT 做开发。通过 Custom Fields and Logic 这类 Fiori 应用,关键用户可以直接在浏览器里写 ABAP 代码,自助实现校验、默认值、计算逻辑等扩展。这背后真正跑的,就是一个专门为关键用户设计的受限语…...

从备份到部署:用Clonezilla为网吧/机房批量克隆系统镜像的实战流程

从备份到部署&#xff1a;用Clonezilla为网吧/机房批量克隆系统镜像的实战流程在网吧、学校机房或企业IT部门中&#xff0c;面对数十台甚至上百台配置相同的计算机&#xff0c;如何高效完成系统部署和环境统一&#xff1f;传统逐台安装的方式不仅耗时费力&#xff0c;还难以保证…...

如何集成OpenClaw?2026年腾讯云部署及配置Token Plan保姆级步骤

如何集成OpenClaw&#xff1f;2026年腾讯云部署及配置Token Plan保姆级步骤。OpenClaw是开源的个人AI助手&#xff0c;Hermes Agent则是一个能自我进化的AI智能体框架。阿里云提供计算巢、轻量服务器及无影云电脑三种部署OpenClaw 与 Hermes Agent的方案、百炼Token Plan兼容主…...

告别硬编码!在UE Niagara中创建可复用的自定义模块库(以动态力场为例)

告别硬编码&#xff01;在UE Niagara中创建可复用的自定义模块库&#xff08;以动态力场为例&#xff09;在虚幻引擎的视觉特效制作中&#xff0c;Niagara系统以其强大的粒子模拟能力成为特效师的核心工具。然而&#xff0c;随着项目复杂度提升&#xff0c;频繁复制粘贴相同逻辑…...

不止是选择器:用Unity Dropdown组件打造一个可交互的游戏设置菜单(附完整C#脚本)

不止是选择器&#xff1a;用Unity Dropdown组件打造一个可交互的游戏设置菜单在游戏开发中&#xff0c;设置菜单是玩家与游戏交互的重要桥梁。一个设计精良的设置菜单不仅能提升用户体验&#xff0c;还能让玩家根据个人偏好调整游戏参数。Unity的Dropdown组件常被简单用作选择器…...

ARM SME架构向量点积指令SVDOT与UDOT深度解析

1. ARM SME架构中的向量点积指令解析在ARMv9架构引入的SME&#xff08;Scalable Matrix Extension&#xff09;扩展中&#xff0c;向量点积运算作为核心计算单元获得了显著增强。我最近在优化一个图像卷积算法时&#xff0c;深入研究了SVDOT和UDOT这两条指令的实际表现。与传统…...