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

力扣-94、144、145-前中后序遍历

二叉树遍历方法总结

 二叉树的遍历总体上分为深度优先遍历和广度优先遍历。常见的前中后序三种遍历方式就属于深度优先遍历,遍历过程中是顺着一条路径一直遍历到空节点然后向上回溯继续顺着遍历上一个节点的其他方向。层序遍历属于广度优先遍历,先遍历完同一层的节点,再接着遍历下一层节点。
 本文主要介绍二叉树三种深度优先遍历方式的实现方式:递归方式和非递归方式。
 递归方式实现如下。
 前序遍历-力扣144:

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new LinkedList<>();if (root == null) {return result;}preOrder(root,result);return result;}private void preOrder(TreeNode current,List<Integer> result) {if (current != null) {result.add(current.val);preOrder(current.left,result);preOrder(current.right,result);}}
}

 中序遍历-力扣94,就是把前序中的处理节点的顺序调整一下。

private void inOrder(TreeNode current,List<Integer> result) {if (current != null) {          inOrder(current.left,result);result.add(current.val);inOrder(current.right,result);}
}

 后序遍历-力扣145,将节点处理顺序调整到最后:

private void inOrder(TreeNode current,List<Integer> result) {if (current != null) {          inOrder(current.left,result);           inOrder(current.right,result);result.add(current.val);}
}

 非递归方式实现如下。
 前序遍历-力扣144,利用栈保存访问过的节点,每访问一个节点,就处理一个。

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new LinkedList<>();if (root == null) {return result;}Deque<TreeNode> stack = new LinkedList<>();stack.push(root);while (!stack.isEmpty()) {TreeNode tempNode = stack.pop();result.add(tempNode.val);if (tempNode.right != null) {stack.push(tempNode.right);}if (tempNode.left != null) {stack.push(tempNode.left);}}return result;}
}

 中序遍历-力扣94

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

 后序遍历-力扣145,后序遍历可以当成是把前序遍历顺序改变一下,从前序的中左右变成中右左,然后再把结果倒置。

class Solution {//后序遍历public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new LinkedList<>();if (root == null) {return result;}Deque<TreeNode> stack = new LinkedList<>();stack.push(root);TreeNode cur = root;while (!stack.isEmpty()) {TreeNode tempNode = stack.pop();result.add(tempNode.val);if (tempNode.left != null) {stack.push(tempNode.left);}if (tempNode.right != null) {stack.push(tempNode.right);}}Collections.reverse(result);return result;}}

相关文章:

力扣-94、144、145-前中后序遍历

二叉树遍历方法总结 二叉树的遍历总体上分为深度优先遍历和广度优先遍历。常见的前中后序三种遍历方式就属于深度优先遍历&#xff0c;遍历过程中是顺着一条路径一直遍历到空节点然后向上回溯继续顺着遍历上一个节点的其他方向。层序遍历属于广度优先遍历&#xff0c;先遍历完同…...

什么是线程?为什么需要线程?和进程的区别?

目录 前言 一.线程是什么&#xff1f; 1.1.为什么需要线程 1.2线程的概念 1.3线程和进程的区别 二.线程的生命周期 三.认识多线程 总结 &#x1f381;个人主页&#xff1a;tq02的博客_CSDN博客-C语言,Java,Java数据结构领域博主 &#x1f3a5; 本文由 tq02 原创&#xf…...

【业务功能篇61】SpringBoot项目流水线 dependencyManagement 标签整改依赖包版本漏洞问题

业务场景&#xff1a;当前我们项目引入了公司自研的一些公共框架组件&#xff0c;比如SSO单点登录jar包&#xff0c;文件上传服务jar包等公共组件&#xff0c;开发新功能&#xff0c;本地验证好之后&#xff0c;部署流水线&#xff0c;报出一些jar包版本的整改漏洞问题&#xf…...

uniapp使用getStorage对属性赋值无效

1正常set(get)storage都是可以正常使用的 2.但对属性进行赋值的时候&#xff0c;却发现this.name并没有发生变化 3. 在里面打印this发现&#xff0c;在set*getStorage中并不能拿到this. 4.优化代码 这样就可以给this.name成功赋值...

20230802-下载并安装android-studio

下载 android-studio 安装包 https://developer.android.google.cn/studio/ 安装android-studio 双击安装包 D:\Android Studio...

python 第九章 —— GUI界面开发(tkinter详解)

文章目录 前言一、GUI与CLI对比二、GUI原理三、tkinter基本使用1.主窗口2.控件(1)button(2)布局(3)Frame(以微信布局为例)(4)Label(5)Entry(6)Text(7)Checkbutton(8)Radiobutton(9)Listbox(10)Scrollbar(11)Canvas...

线段树合并例题

https://www.luogu.com.cn/problem/P3224 1. 永无乡 题意&#xff1a; 给 n 个岛屿&#xff0c;每个岛有一个标号&#xff0c;初始修有 m 条路&#xff0c;有两个操作&#xff0c;操作1 为 给两个岛屿之间修路&#xff0c;操作2为求出 所有能从当前岛屿到达的岛 中标号第k小的…...

Stable Diffusion 硬核生存指南:WebUI 中的 VAE

本篇文章聊聊 Stable Diffusion 生态中呼声最高、也是最复杂的开源模型管理图形界面 “stable-diffusion-webui” 中和 VAE 相关的事情。 写在前面 Stable Diffusion 生态中有一个很重要的项目&#xff0c;它对于 SD 生态繁荣做出的贡献可以说居功至伟&#xff0c;自去年八月…...

vue项目 前端加前缀(包括页面及静态资源)

具体步骤 Vue 中配置 &#xff08;1&#xff09;更改router模式&#xff0c;添加前缀 位置&#xff1a;router文件夹下面的index.js const router new Router({base: /nhtjfx/, // 路由前缀mode: history, // 采用history模式URL的路径才跟配置的对应上&#xff0c;不然UR…...

使用文心一言等智能工具指数级提升嵌入式/物联网(M5Atom/ESP32)和机器人操作系统(ROS1/ROS2)学习研究和开发效率

以M5AtomS3为例&#xff0c;博客撰写效率提升10倍以上&#xff1a; 0. Linux环境Arduino IDE中配置ATOM S3_zhangrelay的博客-CSDN博客 1. M5ATOMS3基础01按键_zhangrelay的博客-CSDN博客 2. M5ATOMS3基础02传感器MPU6886_zhangrelay的博客-CSDN博客 3. M5ATOMS3基础03给RO…...

【Rust 基础篇】Rust动态大小类型:理解动态大小类型与编写安全的代码

导言 Rust是一种以安全性和高效性著称的系统级编程语言&#xff0c;其设计哲学是在不损失性能的前提下&#xff0c;保障代码的内存安全和线程安全。在Rust中&#xff0c;动态大小类型&#xff08;DST&#xff09;是一种特殊的类型&#xff0c;它的大小在编译时无法确定&#x…...

【Python】使用nuitka打包Python程序为EXE可执行程序

1.说明 写好的Python程序如果想要拿到其他电脑上运行&#xff0c;那还得安装一下Python环境和各种库&#xff0c;这是比较麻烦的&#xff0c;所以有必要把它打包成一个可执行的exe文件。可以打包exe的库有好多个&#xff0c;比如说pyinstaller、cx_Freeze等。 pyinstaller打包…...

背景图片及精灵图

.picture {width: 48px;height: 48px;background-image: url(../images/精灵图-侧边功能.png); }为一个有宽高的div设置了背景图片&#xff0c;背景图片只作用在div的content区域内&#xff0c;不作用在padding和border上。 知识点&#xff1a; 背景图使用精灵图&#xff08;…...

简要介绍 | 生成模型的演进:从自编码器(AE)到变分自编码器(VAE)和生成对抗网络(GAN),再到扩散模型

注1:本文系“简要介绍”系列之一,仅从概念上对生成模型(包括AE, VAE, GAN,以及扩散模型)进行非常简要的介绍,不适合用于深入和详细的了解。 生成模型的演进:从自编码器(AE)到变分自编码器(VAE)和生成对抗网络(GAN),再到扩散模型 一、背景介绍 生成模型在机器学习领域…...

8.2Thread类的常见属性

1. 2.前台线程和后台线程 前台线程:影响进程结束(如果前台线程没有执行完,进程不结束). 后台线程(守护线程):不影响线程结束. 创建线程默认是前台线程. 修改成后台线程:thread.setDaetrue);...

博客摘录「 mvvm框架工作原理及优缺」2023年7月31日

mvvm 的核心是数据劫持、数据代理、数据编译和"发布订阅模式"。 1、数据劫持——就是给对象属性添加get,set钩子函数。 ● 1、观察对象&#xff0c;给对象增加 Object.defineProperty ● 2、vue的特点就是新增不存在的属性不会给该属性添加 get 、 set 钩子函数。…...

第12章 Linux 实操篇-Linux磁盘分区、挂载

12.1 Linux 分区 12.1.1 原理介绍 (1) Linux来说无论有几个分区&#xff0c;分给哪一目录使用,它归根结底就只有一个根目录&#xff0c;一个独立且唯一的文件结构, Linux中每个分区都是用来组成整个文件系统的一部分。 (2) Linux采用了一种叫“载入”的处理方法&#xff0c;…...

使用express搭建后端服务

目录 1 创建工程目录2 初始化3 安装express依赖4 启动服务5 访问服务总结 上一篇我们利用TDesign搭建了前端服务&#xff0c;现在的开发讲究一个前后端分离&#xff0c;后端的话需要单独搭建服务。后端服务的技术栈还挺多&#xff0c;有java、php、python、nodejs等。在众多的技…...

深度学习——划分自定义数据集

深度学习——划分自定义数据集 以人脸表情数据集raf_db为例&#xff0c;初始目录如下&#xff1a; 需要经过处理后返回 train_images, train_label, val_images, val_label 定义 read_split_data(root: str, val_rate: float 0.2) 方法来解决&#xff0c;代码如下&#xff1a…...

Jmeter性能测试之正则表达式提取器

目录 前言 1. Jmeter正则表达式提取器 2. 入门实例 3. 进阶实例 前言 Jmeter正则表达式提取器属于Jmeter后置处理器&#xff08;post processors&#xff09;的一种&#xff0c;用于将取样器请求到的结果以正则表达式的方式读取出来。 1. Jmeter正则表达式提取器 1. 作用…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

快刀集(1): 一刀斩断视频片头广告

一刀流&#xff1a;用一个简单脚本&#xff0c;秒杀视频片头广告&#xff0c;还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农&#xff0c;平时写代码之余看看电影、补补片&#xff0c;是再正常不过的事。 电影嘛&#xff0c;要沉浸&#xff0c;…...