算法通关村第七关—迭代实现二叉树的遍历(黄金)
迭代实现二叉树的遍历
迭代法实现前序遍历
前序遍历是中左右,如果还有左子树就一直向下找。完了之后再返回从最底层逐步向上向右找。不难写出如下代码:(注意代码中,空节点不入栈)
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}。

得到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;
}
相关文章:
算法通关村第七关—迭代实现二叉树的遍历(黄金)
迭代实现二叉树的遍历 迭代法实现前序遍历 前序遍历是中左右,如果还有左子树就一直向下找。完了之后再返回从最底层逐步向上向右找。不难写出如下代码:(注意代码中,空节点不入栈) public List<Integer>preorde…...
Java期末复习题之封装
点击返回标题->23年Java期末复习-CSDN博客 第1题. 定义一个类Person,定义name和age私有属性,定义有参的构造方法对name和age进行初始化。在测试类中创建该类的2个对象,姓名、年龄分别为lili、19和lucy、20,在屏幕打印出2个对象的姓名和年龄…...
湖科大计网:计算机网络概述
一、计算机网络的性能指标 一、速率 有时候数据量也认为是以10为底的,看怎么好算。(具体吉大考试用什么待商榷) 二、带宽 在模拟信号系统中带宽的含义,本课程中用到的地方是:香农定理和奈奎斯特定理公式的应用之中。 …...
每日一道c语言
任务描述 题目描述:输入10个互不相同的整数并保存在数组中,找到该最大元素并删除它,输出删除后的数组 相关知识(略) 编程要求 请仔细阅读右侧代码,结合相关知识,在Begin-End区域内进行代码补充…...
(C)一些题11
1. #include<stdio.h> #include<string.h> void main() { char *s1"ABCDEF",*s2"aB"; s1; s2; puts(s1); puts(s2); printf("%d\n",strcmp(s1,s2)); } 答案࿱…...
多级路由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 按照官网的脚本无法安装。 无奈,从github下载安装包来安装。 Homebrew 结果,还需要先安装 Xcode command 命令行工具 xcode-select --install安装完了,却无法执行。 修改配置文件 cd vi .zshrc添加如下内…...
【python交互界面】实现动态观察图像在给定HSV范围的区域显示
HSV颜色空间 与RGB颜色空间相比,HSV颜色空间更适合进行颜色分析和提取特定颜色的目标。在HSV空间中,颜色信息被分布在不同的通道上,使我们能够更准确地定义颜色的范围,并使用阈值操作轻松地分离出我们感兴趣的区域部分。 HSV三个通…...
Vue3中定义变量是选择ref还是reactive?
目录 ref和reactive的优势 1. ref 优势: 应用场景: 示例: 2. reactive 优势: 应用场景: 示例: ref和reactive的劣势 1. ref 2. reactive 应用案例 总结 Vue3中定义变量可以选择使用ref或reac…...
数据结构 | 查漏补缺之哈希表、最短路径、二叉树与森林的转换
哈希表是什么? 或者说 设图采用邻接表的存储结构,写对图的删除顶点和删除边的算法步骤 删除边 删除点 最短路径问题 参考博文 迪杰斯特拉(Dijkstra)算法_dijkstra算法-CSDN博客 Dijkstra(迪杰斯特拉)算法 定义一个点为源点,算源…...
SpringCloud
五大组件 注册/配置中心 Nacos 、Eureka远程调用 Feign负载均衡 Ribbon服务保护 sentinel(实现限流、降级、熔断)网关 gateway 注册中心 Eureka 服务注册:服务提供者把自己的信息注册到Eureka,由Eureka来保存这些信息服务发现…...
fastadmin嵌套关联查询,thinkPHP5嵌套关联查询
fastadmin嵌套关联查询 thinkPHP5嵌套关联查询 笔记记录 嵌套关联查询 A -> B -> C A 表关联B表 B表关联C表 同时把A/B/C表相关的数据展现出来 B表的model B表关联C表 我的C表是B表的自身关联。也是一个表,所以为C表 namespace app…...
Power BI - 5分钟学习拆分列
每天5分钟,今天介绍Power BI拆分列功能。 什么是拆分列? 有时导入Power BI的数据表中,某列内容都包含同样的特殊字符如 /&/-/_等,可以利用这个特殊字符进行拆分列的操作,获得我们想要的信息。 操作举例…...
ELK(四)—els基本操作
目录 elasticsearch基本概念RESTful API创建非结构化索引(增)创建空索引(删)删除索引(改)插入数据(改)数据更新(查)搜索数据(id)&…...
【100天精通Python】Day75:Python机器学习-第一个机器学习小项目_鸾尾花分类项目(上)
目录 1 机器学习中的Helloworld _鸾尾花分类项目 2 导入项目所需类库和鸾尾花数据集 2.1 导入类库 2.2 scikit-learn 库介绍 (1)主要特点: (2)常见的子模块: 3 导入鸾尾花数据集 3.1 概述数据 3.…...
gitlab高级功能之容器镜像仓库
今天给大家介绍一个gitlab的高级功能 - Container Registry,该功能可以实现docker镜像的仓库功能,将gitlab上的代码仓的代码通过docker构建后并推入到容器仓库中,好处就是无需再额外部署一套docker仓库。 文章目录 1. 参考文档2. Container R…...
线程的使用(二)
新增实现方式之实现Callable接口 特点 1、可以有返回值。 2、方法可以抛异常。 3、支持泛型的返回值。 4、需借助FutureTask类,比如获取返回值。 步骤 1、创建一个实现Callable接口的实现类。 2、重写call方法, 将此线程需执行的操作声明在call&…...
k8s之镜像拉取时使用secret
k8s之secret使用 一、说明二、secret使用2.1 secret类型2.2 创建secret2.3 配置secret 一、说明 从公司搭建的网站镜像仓库,使用k8s部署服务时拉取镜像失败,显示未授权: 需要在拉取镜像时添加认证信息. 关于secret信息,参考: https://www.…...
mysql面试题——MVCC
一:什么是MVCC? 多版本并发控制,更好的方式去处理读-写冲突,就是为了查询一些正在被另一个事务更新的行,并且可以看到它们被更新之前的值,这样在做查询的时候就不用等待另一个事务释放锁。 二:…...
【华为数据之道学习笔记】1-2华为数字化转型与数据治理
传统企业通过制造先进的机器来提升生产效率,但是未来,如何结构性地提升服务和运营效率,如何用更低的成本获取更好的产品,成了时代性的问题。数字化转型归根结底就是要解决企业的两大问题:成本和效率,并围绕…...
从“工具辅助”到“智慧赋能”:青软青之深度集成LIMS、ELN、AUTO等核心系统,打造全场景智慧实验室新范式
在科研创新迭代加速、检验检测产业升级纵深推进的今天,实验室作为创新源头,其运行效率与管理水平直接决定研发效能与质量。传统依赖人工记录、纸质流转和信息孤岛的模式,已难以适应复杂实验需求与严苛合规监管。智慧实验室,正成为…...
别再让MCSDK电流环PI参数拖后腿了!手把手教你从电机参数到代码配置的完整调参流程
从电机参数到代码实现:MCSDK电流环PI参数优化实战指南 在电机控制领域,电流环的性能直接影响着整个系统的响应速度、稳定性和能效表现。许多工程师在使用STM32的MCSDK进行FOC开发时,往往满足于"电机能转"的基本状态,却忽…...
技术洞察:zyfun如何重构跨平台视频播放体验
技术洞察:zyfun如何重构跨平台视频播放体验 【免费下载链接】zyfun 跨平台桌面端视频资源播放器,免费高颜值. 项目地址: https://gitcode.com/gh_mirrors/zy/zyfun 在数字娱乐快速发展的今天,跨平台视频播放器面临着系统兼容性、性能优化和用户体…...
text2vec-base-chinese终极指南:如何用768维向量彻底改变中文语义理解
text2vec-base-chinese终极指南:如何用768维向量彻底改变中文语义理解 【免费下载链接】text2vec-base-chinese 项目地址: https://ai.gitcode.com/hf_mirrors/ai-gitcode/text2vec-base-chinese 还在为中文文本的语义匹配而头疼吗?传统的基于关…...
当相机位姿已知:利用COLMAP从稀疏到稠密重建的实战指南
1. 环境准备与数据格式转换 在开始COLMAP重建之前,我们需要确保环境配置正确,并完成相机位姿数据的格式转换。COLMAP支持Windows、Linux和macOS系统,但为了获得最佳性能,建议使用配备NVIDIA显卡的机器,并安装CUDA加速版…...
基于MATLAB/Simulink的双馈异步感应发电机直接功率控制仿真探索
Direct_Power_Control_of_DFIG:基于MATLAB/Simulink的双馈异步感应发电机的直接功率控制仿真模型 仿真条件:MATLAB/Simulink R2015b在电力系统研究领域,双馈异步感应发电机(DFIG)因其独特的性能优势而备受关注。直接功…...
4款降AI率工具实测横评:最便宜和最贵的效果差多少?
花了几百块,测了一圈,现在把结果告诉你。 降AI率工具、降AI工具保姆级测评2026、降AI这个需求,不同工具之间差距其实挺明显的,不是"随便用一个都一样"。 我的结论:嘎嘎降AI(www.aigcleaner.com…...
Java边缘容器化部署卡顿难题(2024最新LTS版HotSpot深度调优白皮书)
第一章:Java边缘容器化部署卡顿难题(2024最新LTS版HotSpot深度调优白皮书)在边缘计算场景下,资源受限的ARM64设备(如Jetson Orin、Raspberry Pi 5)运行JDK 21.0.3 LTS(2024年4月发布)…...
千问3.5-2B轻量化部署教程:边缘设备适配可能性分析与CPU回退方案说明
千问3.5-2B轻量化部署教程:边缘设备适配可能性分析与CPU回退方案说明 1. 模型简介 千问3.5-2B是Qwen系列中的小型视觉语言模型,专为边缘计算场景优化设计。这个2B参数量的版本在保持视觉理解能力的同时,大幅降低了硬件需求。 模型核心能力…...
StructBERT-WebUI部署案例:AI客服中台语义路由模块集成实践
StructBERT-WebUI部署案例:AI客服中台语义路由模块集成实践 1. 项目背景与价值 在现代AI客服系统中,语义理解是核心能力之一。当用户提出"我的订单怎么还没到"时,系统需要准确理解这其实是在询问"物流状态",…...
