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

庖丁解牛-二叉树的遍历

庖丁解牛-二叉树的遍历

在这里插入图片描述

〇、前言

01 文章内容

  • 一般提到二叉树的遍历,我们是在说
    • 前序遍历、中序遍历、后序遍历和层序遍历
  • 或者说三序遍历+层序遍历,毕竟三序和层序的遍历逻辑相差比较大
  • 下面讨论三序遍历的递归方法、非递归方法和非递归迭代的统一方法
  • 然后再讨论一下层序的一般迭代方法(通过队列)

02 力扣网址

  • 144. 二叉树的前序遍历 - 力扣(LeetCode)
  • 94. 二叉树的中序遍历 - 力扣(LeetCode)
  • 145. 二叉树的后序遍历 - 力扣(LeetCode)

一、前序遍历

01 递归实现

  • 递归的基本逻辑是比较简单的,但是注意根据题目的需求不同,实现方式是存在差异的
  • 如果题目要求主函数返回一个结果列表,那么就要构造一个辅助函数来帮助实现
  • 如果题目只要求函数打印前序遍历的序列,那么一个函数就足够了
(1) 返回列表版本1

返回列表版本:辅助函数携带结果列表

public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();inorderTraversalHelper(root,result);return result;}
void preorderTraversalHelper(TreeNode root,List<Integer> result){if(root == null) return;result.add(root.val);inorderTraversalHelper(root.left,result);inorderTraversalHelper(root.right,result);return;
}
(2) 返回列表版本2

返回列表版本:设置全局变量

List<Integer> result = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {inorderTraversalHelper(root,result);return result;
}
void preorderTraversalHelper(TreeNode root){if(root == null) return;result.add(root.val);inorderTraversalHelper(root.left,result);inorderTraversalHelper(root.right,result);return;
}
(3) 纯真打印版本
public List<Integer> preorderTraversal(TreeNode root) {inorderTraversalHelper(root,result);return result;
}
void preorderTraversal(TreeNode root){if(root == null) return;System.out.print(root.val);inorderTraversalHelper(root.left,result);inorderTraversalHelper(root.right,result);return;
}
(4) 面向对象版本
class Solution {class TraverBox{List<Integer> list;TraverBox(){list = new ArrayList<>();}void preorderTraversalHelper(TreeNode root) {list.add(root.val);}void preTraverHelper(TreeNode root) {if(root == null) return;list.add(root.val);preTraverHelper(root.left);preTraverHelper(root.right);}List<Integer> preTraver(TreeNode root) {preTraverHelper(root);return list;}}public List<Integer> preorderTraversal(TreeNode root) {TraverBox tox = new TraverBox();tox.preTraver(root);return tox.list;}
}

02 非递归实现

(1) 一般迭代法

(2) 统一迭代法
public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new LinkedList<>();Stack<TreeNode> stack = new Stack<>();TreeNode subRoot = new TreeNode();if (root != null) stack.push(root); //将根结点入栈while(!stack.isEmpty()){subRoot = stack.pop(); //弹出获取栈顶结点if(subRoot != null){//===右===if(subRoot.right != null){// 添加右结点(空结点不入栈)stack.push(subRoot.right);}//===左===if(subRoot.left != null){// 添加左节点(空结点不入栈)stack.push(subRoot.left);}//===中===stack.push(subRoot); // 添加中结点stack.push(null); // 中结点访问过,但是还没有处理,加入空结点做为标记。}else{ // 只有遇到空结点的时候,才将下一个结点放进结果集result.add(stack.pop().val); //重新取出栈中元素,加入到结果集}}return result;
}

二、中序遍历

01 递归实现

(1) 返回列表版本1

返回列表版本:辅助函数携带结果列表

public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();inorderTraversalHelper(root,result);return result;}
void preorderTraversalHelper(TreeNode root,List<Integer> result){if(root == null) return;inorderTraversalHelper(root.left,result);result.add(root.val);inorderTraversalHelper(root.right,result);return;
}
(2) 返回列表版本2

返回列表版本:设置全局变量

List<Integer> result = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {inorderTraversalHelper(root,result);return result;
}
void preorderTraversalHelper(TreeNode root){if(root == null) return;inorderTraversalHelper(root.left,result);result.add(root.val);inorderTraversalHelper(root.right,result);return;
}
(3) 纯真打印版本
void preorderTraversal(TreeNode root){if(root == null) return;inorderTraversalHelper(root.left,result);System.out.print(root.val);inorderTraversalHelper(root.right,result);return;
}

02 非递归实现

(1) 一般迭代法
void inOrderNonRecur(){Stack<TreeNode> stack = new Stack<>();TreeNode subRoot = root;if (subRoot != null) {while (!stack.isEmpty() || subRoot != null) {if (subRoot != null) {stack.push(subRoot);subRoot = subRoot.left;} else {subRoot = stack.pop();System.out.print("【"+subRoot.val+"】");subRoot = subRoot.right;}}}
}
(2) 统一迭代法

带注释版本

public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new LinkedList<>();Stack<TreeNode> stack = new Stack<>();TreeNode subRoot = new TreeNode();if (root != null) stack.push(root);while (!stack.isEmpty()) {subRoot = stack.pop(); // 将该节点弹出,避免重复操作,下面再将右中左节点添加到栈中if (subRoot != null) {//===右===if(subRoot.right != null){// 添加右节点(空节点不入栈)stack.push(subRoot.right);}//===中===stack.push(subRoot); // 添加中节点stack.push(null); // 中节点访问过,但是还没有处理,加入空节点做为标记。//===左===if(subRoot.left != null){// 添加左节点(空节点不入栈)stack.push(subRoot.left);}} else { // 只有遇到空节点的时候,才将下一个节点放进结果集result.add(stack.pop().val); // 加入到结果集}}return result;
}

无注释版本

public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new LinkedList<>();Stack<TreeNode> stack = new Stack<>();TreeNode subRoot = new TreeNode();if (root != null) stack.push(root);while (!stack.isEmpty()) {subRoot = stack.pop();if (subRoot != null) {if(subRoot.right != null) stack.push(subRoot.right);stack.push(subRoot);stack.push(null);if(subRoot.left != null) stack.push(subRoot.left);} else {result.add(stack.pop().val);}}return result;
}

三、后序遍历

01 递归实现

(1) 返回列表版本1

返回列表版本:辅助函数携带结果列表

public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();inorderTraversalHelper(root,result);return result;}
void preorderTraversalHelper(TreeNode root,List<Integer> result){if(root == null) return;inorderTraversalHelper(root.left,result);inorderTraversalHelper(root.right,result);result.add(root.val);return;
}
(2) 返回列表版本2

返回列表版本:设置全局变量

List<Integer> result = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {inorderTraversalHelper(root,result);return result;
}
void preorderTraversalHelper(TreeNode root){if(root == null) return;inorderTraversalHelper(root.left,result);inorderTraversalHelper(root.right,result);result.add(root.val);return;
}
(3) 纯真打印版本
void preorderTraversal(TreeNode root){if(root == null) return;inorderTraversalHelper(root.left,result);inorderTraversalHelper(root.right,result);System.out.print(root.val);return;
}

02 非递归实现

(1) 一般迭代法
public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root != null) {Stack<TreeNode> stack = new Stack<TreeNode>();stack.push(root);TreeNode subRoot = null;while (!stack.isEmpty()) {subRoot = stack.peek();if (subRoot.left != null && root != subRoot.left && root != subRoot.right) {stack.push(subRoot.left);} else if (subRoot.right != null && root != subRoot.right) {stack.push(subRoot.right);} else {result.add(stack.pop().val);root = subRoot;}}}return result;
}
(2) 双栈迭代法
public List<Integer> postOrderNonRecurByTwoStack(){List<Integer> result = new ArrayList<>();TreeNode subRoot = root;if (subRoot != null) {Stack<TreeNode> s1 = new Stack<TreeNode>();Stack<TreeNode> s2 = new Stack<TreeNode>();s1.push(subRoot);while (!s1.isEmpty()) {subRoot = s1.pop();s2.push(subRoot);if (subRoot.left != null) {s1.push(subRoot.left);}if (subRoot.right != null) {s1.push(subRoot.right);}}while (!s2.isEmpty()) {result.add(s2.pop().val);}}
}
(3) 统一迭代法
public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new LinkedList<>();Stack<TreeNode> stack = new Stack<>();TreeNode subRoot = new TreeNode();if (root != null) stack.push(root); //将根结点入栈while(!stack.isEmpty()){subRoot = stack.pop(); //弹出获取栈顶结点if(subRoot != null){//===中===stack.push(subRoot); // 添加中结点stack.push(null); // 中结点访问过,但是还没有处理,加入空结点做为标记。//===右===if(subRoot.right != null){// 添加右结点(空结点不入栈)stack.push(subRoot.right);}//===左===if(subRoot.left != null){// 添加左节点(空结点不入栈)stack.push(subRoot.left);}}else{ // 只有遇到空结点的时候,才将下一个结点放进结果集result.add(stack.pop().val); //重新取出栈中元素,加入到结果集}}return result;
}

四、层序遍历

01 不分层输出

class Solution {public int[] levelOrder(TreeNode root) {//if(root == null) return new int[]{};ArrayList<Integer> result = new ArrayList<Integer>();Queue<TreeNode> queue = new LinkedList<TreeNode>();TreeNode subRoot = new TreeNode();if(root != null) queue.offer(root);while(!queue.isEmpty()){subRoot = queue.poll();result.add(subRoot.val);if(subRoot.left != null) queue.add(subRoot.left);if(subRoot.right != null) queue.add(subRoot.right);}int[] dest = new int[result.size()];for(int i = 0 ; i < result.size() ; i++){dest[i] = result.get(i);}return dest;}
}

02 分层输出

public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> ret = new ArrayList<List<Integer>>();if (root == null) {return ret;}Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(root);while (!queue.isEmpty()) {List<Integer> level = new ArrayList<Integer>();int currentLevelSize = queue.size();for (int i = 1; i <= currentLevelSize; ++i) {TreeNode node = queue.poll();level.add(node.val);if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}ret.add(level);}return ret;
}

相关文章:

庖丁解牛-二叉树的遍历

庖丁解牛-二叉树的遍历 〇、前言 01 文章内容 一般提到二叉树的遍历&#xff0c;我们是在说 前序遍历、中序遍历、后序遍历和层序遍历 或者说三序遍历层序遍历&#xff0c;毕竟三序和层序的遍历逻辑相差比较大下面讨论三序遍历的递归方法、非递归方法和非递归迭代的统一方法然…...

一文了解LM317T的引脚介绍、参数解读

LM317T是一种线性稳压器件&#xff0c;它具有稳定输出电压的特性。LM317T可以通过调整其输出电阻来确保输出电压的稳定性&#xff0c;因此被广泛应用于各种电子设备中。 LM317T引脚图介绍 LM317T共有3个引脚&#xff0c;分别是&#xff1a; 输入引脚&#xff08;输入电压V_in&…...

【2024.02.22】定时执行专家 V7.0 发布 - TimingExecutor V7.0 Release - 龙年春节重大更新版本

目录 ▉ 新版本 V7.0 下载地址 ▉ V7.0 新功能 ▼2024-02-21 V7.0 - 更新日志▼ ▉ V7.0 新UI设计 ▉ 新版本 V7.0 下载地址 BoomWorks软件的最新版本-CSDN博客文章浏览阅读10w次&#xff0c;点赞9次&#xff0c;收藏41次。▉定时执行专家—毫秒精度、专业级的定时任务执行…...

☀️将大华摄像头画面接入Unity 【1】配置硬件和初始化摄像头

一、硬件准备 目前的设想是后期采用网口供电的形式把画面传出来&#xff0c;所以这边我除了大华摄像头还准备了POE供电交换机&#xff0c;为了方便索性都用大华的了&#xff0c;然后全都连接电脑主机即可。 二、软件准备 这边初始化摄像头需要用到大华的Configtool软件&#…...

直流电流电压变送器4-20mA 10V信号隔离转换模拟量精度变送器

品牌&#xff1a;泰华仪表 型号&#xff1a;TB-IP(U)XX 产地&#xff1a;中国大陆 省份&#xff1a;安徽省 地市&#xff1a;宿州市 颜色分类&#xff1a;4-20mA转4-20mA,4-20mA转0-10V,4-20mA转0-20mA,4-20mA转0-5V,0-20mA转0-20mA,0-20mA转4-20mA,0-20mA转0-10V,0-20mA转…...

1.1 计算机网络的概念、功能、组成和分类

文章目录 1.1 计算机网络的概念、功能、组成和分类&#xff08;一&#xff09;计算机网络的概念&#xff08;二&#xff09;计算机网络的功能&#xff08;三&#xff09;计算机网络的组成1.组成部分2.工作方式3.功能组成 &#xff08;四&#xff09;计算机网络的分类 总结 1.1 …...

排序算法整理

排序种类排序特性代码背景 基于插入的排序直接插入排序原理代码 折半查找排序2路查找排序希尔排序(shell) 缩小增量排序原理代码 基于交换的排序冒泡排序原理代码 快速排序&#xff08;重要!&#xff09;原理我的思考 代码 基于选择的排序&#xff08;简单&#xff09;选择排序…...

ONLYOFFICE 桌面应用程序 v8.0 发布:全新 RTL 界面、本地主题、Moodle 集成等你期待的功能来了!

目录 &#x1f4d8; 前言 &#x1f4df; 一、什么是 ONLYOFFICE 桌面编辑器&#xff1f; &#x1f4df; 二、ONLYOFFICE 8.0版本新增了那些特别的实用模块&#xff1f; 2.1. 可填写的 PDF 表单 2.2. 双向文本 2.3. 电子表格中的新增功能 单变量求解&#xff1a;…...

c语言---数组(超级详细)

数组 一.数组的概念二. 一维数组的创建和初始化2.1数组的创建2.2数组的初始化错误的初始化 2.3 数组的类型 三. 一维数组的使用3.1数组的下标3.2数组元素的打印3.2数组元素的输入 四. 一维数组在内存中的存储五. 二维数组的创建5.1二维数组的概念5.2如何创建二维数组 六.二维数…...

神经网络权重初始化

诸神缄默不语-个人CSDN博文目录 &#xff08;如果只想看代码&#xff0c;请直接跳到“方法”一节&#xff0c;开头我介绍我的常用方法&#xff0c;后面介绍具体的各种方案&#xff09; 神经网络通过多层神经元相互连接构成&#xff0c;而这些连接的强度就是通过权重&#xff…...

代码随想录训练营第三十九天|62.不同路径63. 不同路径 II

62.不同路径 1确定dp数组&#xff08;dp table&#xff09;以及下标的含义 从&#xff08;0&#xff0c;0&#xff09;出发到&#xff08;i&#xff0c;j&#xff09;有 dp[i][j]种路径 2确定递推公式 dp[i][j]dp[i-1][j]dp[i][j-1] 3dp数组如何初始化 for(int i0;i<m…...

学习大数据所需的java基础(5)

文章目录 集合框架Collection接口迭代器迭代器基本使用迭代器底层原理并发修改异常 数据结构栈队列数组链表 List接口底层源码分析 LinkList集合LinkedList底层成员解释说明LinkedList中get方法的源码分析LinkedList中add方法的源码分析 增强for增强for的介绍以及基本使用发2.使…...

Python 光速入门课程

首先说一下&#xff0c;为啥小编在即PHP和Golang之后&#xff0c;为啥又要整Python&#xff0c;那是因为小编最近又拿起了 " 阿里天池 " 的东西&#xff0c;所以小编又不得不捡起来大概五年前学习的Python&#xff0c;本篇文章主要讲的是最基础版本&#xff0c;所以比…...

解决vite打包出现 “default“ is not exported by “node_modules/...问题

项目场景&#xff1a; vue3tsvite项目打包 问题描述 // codemirror 编辑器的相关资源 import Codemirror from codemirror;error during build: RollupError: "default" is not exported by "node_modules/vue/dist/vue.runtime.esm-bundler.js", impor…...

c语言strtok的使用

strtok函数的作用为以指定字符分割字符串&#xff0c;含有两个参数&#xff0c;第一个函数为待分割的字符串或者空指针NULL&#xff0c;第二个参数为分割字符集。 对一个字符串首次使用strtok时第一个参数应该是待分割字符串&#xff0c;strtok以指定字符完成第一次分割后&…...

hash,以及数据结构——map容器

1.hash是什么&#xff1f; 定义&#xff1a;hash,一般翻译做散列、杂凑&#xff0c;或音译为哈希&#xff0c;是把任意长度的输入&#xff08;又叫做预映射pre-image&#xff09;通过散列算法变换成固定长度的输出&#xff0c; 该输出就是散列值。这种转换是一种压缩映射&…...

AIoT网关 人工智能物联网网关

AIoT(人工智能物联网)作为新一代技术的代表&#xff0c;正以前所未有的速度改变着我们的生活方式。在这个智能时代&#xff0c;AIoT网关的重要性日益凸显。它不仅是连接智能设备和应用的关键&#xff0c;同时也是实现智能化家居、智慧城市和工业自动化的必备技术。      一…...

基于YOLOv8/YOLOv7/YOLOv6/YOLOv5的鸟类识别系统(Python+PySide6界面+训练代码)

摘要&#xff1a;本文详细阐述了一个利用深度学习进行鸟类识别的系统&#xff0c;该系统集成了最新的YOLOv8算法&#xff0c;并与YOLOv7、YOLOv6、YOLOv5等先前版本进行了性能比较。该系统能够在图像、视频、实时视频流和批量文件中精确地识别和分类鸟类。文中不仅深入讲解了YO…...

核密度分析

一.算法介绍 核密度估计&#xff08;Kernel Density Estimation&#xff09;是一种用于估计数据分布的非参数统计方法。它可以用于多种目的和应用&#xff0c;包括&#xff1a; 数据可视化&#xff1a;核密度估计可以用来绘制平滑的密度曲线或热力图&#xff0c;从而直观地表…...

先进语言模型带来的变革与潜力

用户可以通过询问或交互方式与GPT-4这样的先进语言模型互动&#xff0c;开启通往知识宝库的大门&#xff0c;即时访问人类历史积累的知识、经验与智慧。像GPT-4这样的先进语言模型&#xff0c;能够将人类历史上积累的海量知识和经验整合并加以利用。通过深度学习和大规模数据训…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

免费数学几何作图web平台

光锐软件免费数学工具&#xff0c;maths,数学制图&#xff0c;数学作图&#xff0c;几何作图&#xff0c;几何&#xff0c;AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...

BLEU评分:机器翻译质量评估的黄金标准

BLEU评分&#xff1a;机器翻译质量评估的黄金标准 1. 引言 在自然语言处理(NLP)领域&#xff0c;衡量一个机器翻译模型的性能至关重要。BLEU (Bilingual Evaluation Understudy) 作为一种自动化评估指标&#xff0c;自2002年由IBM的Kishore Papineni等人提出以来&#xff0c;…...