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

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...