当前位置: 首页 > 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. 作用…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...