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

算法通关村第七关—迭代实现二叉树的遍历(黄金)

       迭代实现二叉树的遍历

迭代法实现前序遍历

 前序遍历是中左右,如果还有左子树就一直向下找。完了之后再返回从最底层逐步向上向右找。不难写出如下代码:(注意代码中,空节点不入栈)

public List<Integer>preorderTraversal(TreeNode root){
List<Integer>res = new ArrayList<Integer>();
if(root == null){return res;
}
Deque<TreeNode> stack = new LinkedList<TreeNode>();
TreeNode node = root;
while(!stack.isEmpty() || node != null){while(node != null){res.add(node.val);stack.push(node);node = node.left;}node = stack.pop();node = node.right;
}
return res;
}

迭代法实现中序遍历

 再看中序遍历,中序遍历是左中右,先访问的是二叉树左子树的节点,然后一层一层向下访问,直到到达树左面的最底部,再开始处理节点(也就是在把节点的数值放进s列表中)。在使用迭代法写中序遍历,就需要借用指针的遍历来帮助访问节点,栈则用来处理节点上的元素。看代码:

public List<Integer>inorderTraversal(TreeNode root){
List<Integer> res = new ArrayList<Integer>();
Deque<TreeNode> stack = new LinkedList<TreeNode>();
while (root != null || !stack.isEmpty()){while (root != null){stack.push(root);root root.left;}root = stack.pop();res.add(root.val);root root.right;
}
return res;
}

迭代法实现后序遍历

 后序遍历的非递归实现有三种基本的思路:反转法、访问标记法、和Mos法,可惜,三种理解起来都有些难度。
 访问标记法是最难理解的方法,而Mos法是一个老外发明的巧妙思想:不使用栈,而是用好树中的null指针,但是实现后序仍然非常麻烦,我们这里不再展开,感兴趣的同学可以查一下,
 这里分享一种好理解又好实现的方法:反转法。如下图,我们先观察后序遍历的结果是seq={95743},如果我们将其整体反转的话就是new_seq={34759}。
截屏2023-12-03 15.38.58.png
 得到new_seql的方法和前序遍历思路几乎一致,只不过是左右反了。前序是先中间,再左边然后右边,而这里是先中间,再后边然后左边。那我们完全可以改造一下前序遍历,得到序列new_seq之后再reverse一下就是想要的结果了,代码如下:

public List<Integer>postorderTraversal(TreeNode root){
List<Integer>res = new ArrayList<>();
if (root == null)return res;
Stack<TreeNode>stack = new stack<>();
TreeNode node = root;
while(!stack.isEmpty() || node != null){while(node != null){res.add(node.val);stack.push(node);node = node.right; //是right不是left}node stack.pop();node node.left;
}
//注意反转要用Collections
Collections.reverse(res);
return res;
}

相关文章:

算法通关村第七关—迭代实现二叉树的遍历(黄金)

迭代实现二叉树的遍历 迭代法实现前序遍历 前序遍历是中左右&#xff0c;如果还有左子树就一直向下找。完了之后再返回从最底层逐步向上向右找。不难写出如下代码&#xff1a;&#xff08;注意代码中&#xff0c;空节点不入栈&#xff09; public List<Integer>preorde…...

Java期末复习题之封装

点击返回标题->23年Java期末复习-CSDN博客 第1题. 定义一个类Person,定义name和age私有属性&#xff0c;定义有参的构造方法对name和age进行初始化。在测试类中创建该类的2个对象&#xff0c;姓名、年龄分别为lili、19和lucy、20&#xff0c;在屏幕打印出2个对象的姓名和年龄…...

湖科大计网:计算机网络概述

一、计算机网络的性能指标 一、速率 有时候数据量也认为是以10为底的&#xff0c;看怎么好算。&#xff08;具体吉大考试用什么待商榷&#xff09; 二、带宽 在模拟信号系统中带宽的含义&#xff0c;本课程中用到的地方是&#xff1a;香农定理和奈奎斯特定理公式的应用之中。 …...

每日一道c语言

任务描述 题目描述:输入10个互不相同的整数并保存在数组中&#xff0c;找到该最大元素并删除它&#xff0c;输出删除后的数组 相关知识&#xff08;略&#xff09; 编程要求 请仔细阅读右侧代码&#xff0c;结合相关知识&#xff0c;在Begin-End区域内进行代码补充&#xf…...

(C)一些题11

1. #include<stdio.h> #include<string.h> void main() { char *s1"ABCDEF"&#xff0c;*s2"aB"&#xff1b; s1; s2; puts(s1)&#xff1b; puts(s2)&#xff1b; printf("%d\n",strcmp(s1,s2))&#xff1b; } 答案&#xff1…...

多级路由component页面不加载

项目基于vue-element-admin 新建SubView.vue <template><router-view /> </template><script setup> </script>在父层添加component {path: /sj,component: Layout,redirect: /sj,name: 三级医院评审标准(2022),meta: {title: 三级医院评审标准(…...

【原创】Mac mini M1安装home-brew

Mac mini M1 所需神器 home-brew 按照官网的脚本无法安装。 无奈&#xff0c;从github下载安装包来安装。 Homebrew 结果&#xff0c;还需要先安装 Xcode command 命令行工具 xcode-select --install安装完了&#xff0c;却无法执行。 修改配置文件 cd vi .zshrc添加如下内…...

【python交互界面】实现动态观察图像在给定HSV范围的区域显示

HSV颜色空间 与RGB颜色空间相比&#xff0c;HSV颜色空间更适合进行颜色分析和提取特定颜色的目标。在HSV空间中&#xff0c;颜色信息被分布在不同的通道上&#xff0c;使我们能够更准确地定义颜色的范围&#xff0c;并使用阈值操作轻松地分离出我们感兴趣的区域部分。 HSV三个通…...

Vue3中定义变量是选择ref还是reactive?

目录 ref和reactive的优势 1. ref 优势&#xff1a; 应用场景&#xff1a; 示例&#xff1a; 2. reactive 优势&#xff1a; 应用场景&#xff1a; 示例&#xff1a; ref和reactive的劣势 1. ref 2. reactive 应用案例 总结 Vue3中定义变量可以选择使用ref或reac…...

数据结构 | 查漏补缺之哈希表、最短路径、二叉树与森林的转换

哈希表是什么&#xff1f; 或者说 设图采用邻接表的存储结构&#xff0c;写对图的删除顶点和删除边的算法步骤 删除边 删除点 最短路径问题 参考博文 迪杰斯特拉(Dijkstra)算法_dijkstra算法-CSDN博客 Dijkstra(迪杰斯特拉&#xff09;算法 定义一个点为源点&#xff0c;算源…...

SpringCloud

五大组件 注册/配置中心 Nacos 、Eureka远程调用 Feign负载均衡 Ribbon服务保护 sentinel&#xff08;实现限流、降级、熔断&#xff09;网关 gateway 注册中心 Eureka 服务注册&#xff1a;服务提供者把自己的信息注册到Eureka&#xff0c;由Eureka来保存这些信息服务发现…...

fastadmin嵌套关联查询,thinkPHP5嵌套关联查询

fastadmin嵌套关联查询 thinkPHP5嵌套关联查询 笔记记录 嵌套关联查询 A -> B -> C A 表关联B表 B表关联C表 同时把A&#xff0f;B&#xff0f;C表相关的数据展现出来 B表的model B表关联C表 我的C表是B表的自身关联。也是一个表&#xff0c;所以为C表 namespace app…...

Power BI - 5分钟学习拆分列

每天5分钟&#xff0c;今天介绍Power BI拆分列功能。 什么是拆分列&#xff1f; 有时导入Power BI的数据表中&#xff0c;某列内容都包含同样的特殊字符如 /&/-/_等&#xff0c;可以利用这个特殊字符进行拆分列的操作&#xff0c;获得我们想要的信息。 操作举例&#xf…...

ELK(四)—els基本操作

目录 elasticsearch基本概念RESTful API创建非结构化索引&#xff08;增&#xff09;创建空索引&#xff08;删&#xff09;删除索引&#xff08;改&#xff09;插入数据&#xff08;改&#xff09;数据更新&#xff08;查&#xff09;搜索数据&#xff08;id&#xff09;&…...

【100天精通Python】Day75:Python机器学习-第一个机器学习小项目_鸾尾花分类项目(上)

目录 1 机器学习中的Helloworld _鸾尾花分类项目 2 导入项目所需类库和鸾尾花数据集 2.1 导入类库 2.2 scikit-learn 库介绍 &#xff08;1&#xff09;主要特点&#xff1a; &#xff08;2&#xff09;常见的子模块&#xff1a; 3 导入鸾尾花数据集 3.1 概述数据 3.…...

gitlab高级功能之容器镜像仓库

今天给大家介绍一个gitlab的高级功能 - Container Registry&#xff0c;该功能可以实现docker镜像的仓库功能&#xff0c;将gitlab上的代码仓的代码通过docker构建后并推入到容器仓库中&#xff0c;好处就是无需再额外部署一套docker仓库。 文章目录 1. 参考文档2. Container R…...

线程的使用(二)

新增实现方式之实现Callable接口 特点 1、可以有返回值。 2、方法可以抛异常。 3、支持泛型的返回值。 4、需借助FutureTask类&#xff0c;比如获取返回值。 步骤 1、创建一个实现Callable接口的实现类。 2、重写call方法&#xff0c; 将此线程需执行的操作声明在call&…...

k8s之镜像拉取时使用secret

k8s之secret使用 一、说明二、secret使用2.1 secret类型2.2 创建secret2.3 配置secret 一、说明 从公司搭建的网站镜像仓库&#xff0c;使用k8s部署服务时拉取镜像失败&#xff0c;显示未授权&#xff1a; 需要在拉取镜像时添加认证信息. 关于secret信息,参考: https://www.…...

mysql面试题——MVCC

一&#xff1a;什么是MVCC&#xff1f; 多版本并发控制&#xff0c;更好的方式去处理读-写冲突&#xff0c;就是为了查询一些正在被另一个事务更新的行&#xff0c;并且可以看到它们被更新之前的值&#xff0c;这样在做查询的时候就不用等待另一个事务释放锁。 二&#xff1a…...

【华为数据之道学习笔记】1-2华为数字化转型与数据治理

传统企业通过制造先进的机器来提升生产效率&#xff0c;但是未来&#xff0c;如何结构性地提升服务和运营效率&#xff0c;如何用更低的成本获取更好的产品&#xff0c;成了时代性的问题。数字化转型归根结底就是要解决企业的两大问题&#xff1a;成本和效率&#xff0c;并围绕…...

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

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

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

ffmpeg(四):滤镜命令

FFmpeg 的滤镜命令是用于音视频处理中的强大工具&#xff0c;可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下&#xff1a; ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜&#xff1a; ffmpeg…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

基于SpringBoot在线拍卖系统的设计和实现

摘 要 随着社会的发展&#xff0c;社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统&#xff0c;主要的模块包括管理员&#xff1b;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...

【JVM】Java虚拟机(二)——垃圾回收

目录 一、如何判断对象可以回收 &#xff08;一&#xff09;引用计数法 &#xff08;二&#xff09;可达性分析算法 二、垃圾回收算法 &#xff08;一&#xff09;标记清除 &#xff08;二&#xff09;标记整理 &#xff08;三&#xff09;复制 &#xff08;四&#xff…...