当前位置: 首页 > 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;并围绕…...

马年市场快报分析:欧美组合式一氧化碳及可燃气体报警器指南

马年市场快报分析&#xff1a;欧美组合式一氧化碳及可燃气体报警器指南根据您提供的快报内容&#xff0c;我将从专业角度逐步分析欧美组合式一氧化碳&#xff08;CO&#xff09;及可燃气体报警器的关键信息&#xff0c;包括安全标准、风险因素、探测器区别、安装建议以及相关产…...

ARL灯塔扫不出指纹?手把手教你用Python脚本批量导入指纹库,提升资产识别准确率

ARL灯塔指纹识别优化实战&#xff1a;Python脚本批量导入与精准率提升指南 资产侦察灯塔&#xff08;ARL&#xff09;作为渗透测试领域的重要工具&#xff0c;其核心价值在于准确识别目标资产的技术特征。然而许多中级用户发现&#xff0c;默认指纹库在面对特定行业或新型资产…...

Phi-4-mini-reasoning开源模型优势:轻量级+高精度+低GPU资源占用实测

Phi-4-mini-reasoning开源模型优势&#xff1a;轻量级高精度低GPU资源占用实测 1. 模型概述 Phi-4-mini-reasoning是一款专注于推理任务的文本生成模型&#xff0c;特别擅长处理数学题、逻辑题、多步分析和简洁结论输出。与通用聊天模型不同&#xff0c;它采用了"题目输…...

数据库存储有什么作用

数据库存储就是把数据安全、规范、高效地存起来&#xff0c;方便以后用&#xff0c;核心作用可以分成这几块&#xff1a;1. 持久化保存程序关掉、电脑重启&#xff0c;数据不会丢失不像内存一断电就清空&#xff0c;数据库存在硬盘里长期保存2. 统一管理数据把零散的文件、记录…...

STM32F4读写SD卡:填一填ST官方HAL库的坑

使用STM32读写SD卡在低功耗存储中的应用是比较常见的&#xff0c;但是网上大多数资料都是基于标准库或者基于寄存器的开发。随着嵌入式设备越来越复杂&#xff0c;使用HAL库能够大大降低开发者的学习成本&#xff0c;从而提高开发效率。近年来&#xff0c;ST官方主推以STM32Cub…...

超导电路阵列实验方案 V1.0桌面量子引力实验(自指动力学与类时空关联涌现)

超导电路阵列实验方案 V1.0 桌面量子引力实验&#xff08;自指动力学与类时空关联涌现&#xff09; 方案编号&#xff1a;SR-EXP-QG-001 版本&#xff1a;V1.0 一、核心科学目标 1. 科学目标 在一维/二维超导量子比特阵列中&#xff0c;引入全局量子态测量 实时反馈构建强自指…...

告别滑动窗口!用FastFlow+Vision Transformer实现工业缺陷检测的端到端定位

FastFlow与Vision Transformer&#xff1a;工业缺陷检测的端到端革命 在工业质检领域&#xff0c;传统异常检测方法正面临前所未有的效率瓶颈。想象一下&#xff1a;一条每分钟处理200件产品的生产线&#xff0c;每件产品需要扫描3000个关键点位&#xff0c;而传统滑动窗口算法…...

Pixel Fashion Atelier部署案例:中小企业低成本GPU算力优化生成方案

Pixel Fashion Atelier部署案例&#xff1a;中小企业低成本GPU算力优化生成方案 1. 项目概述与核心价值 Pixel Fashion Atelier是一款专为时尚设计领域打造的AI图像生成工作站&#xff0c;基于Stable Diffusion和Anything-v5模型构建。与传统AI工具不同&#xff0c;它采用独特…...

太方便了!农村自建房设计新神器,二三维设计 + 扫码看模型

还在为农村自建房设计发愁&#xff1f;手绘图纸看不懂、修改慢、施工易出错&#xff1f;飞扬集成设计系统&#xff0c;专为农村自建房打造&#xff0c;一键实现二三维一体化设计&#xff0c;还能扫码查看轻量化 3D 模型&#xff0c;让建房更高效、更直观、更省心&#xff01;一…...

AI字体生成技术应用指南:从问题到解决方案的实践之路

AI字体生成技术应用指南&#xff1a;从问题到解决方案的实践之路 【免费下载链接】Rewrite Neural Style Transfer For Chinese Characters 项目地址: https://gitcode.com/gh_mirrors/rewr/Rewrite 在数字化设计领域&#xff0c;中文字体的个性化定制一直是创意工作者面…...