二叉树的遍历(递归法)

news/2024/2/25 20:42:47/文章来源:https://blog.csdn.net/weixin_44689901/article/details/135584524

递归的三要素:

①确定递归函数的参数和返回值

②确定终止条件

③确定单层递归的逻辑

以前序遍历为例:

1、确定递归函数的参数和返回值:

参数中需要传入list来存放节点的数值,除了这一点就不需要再处理什么数据了也不需要有返回值,因此递归函数的返回类型就是void。

public void traversal(TreeNode cur,List<Integer> list)

2、确定终止条件:

在递归的过程中,如何算是递归结束了呢?当然是当前遍历的节点为空,那么本层递归就要结束了。所以,如果当前遍历的这个节点为空,就直接return。

if(cur==null) return ;

3、确定单层递归的逻辑:

前序遍历是根左右,所以逻辑如下

list.add(cur.val);

traversal(cur.left,list);

traversal(cur.right,list);

二叉树的前序,中序和后序遍历代码如下:

// 前序遍历·递归·LC144_二叉树的前序遍历
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<Integer>();preorder(root, result);return result;}public void preorder(TreeNode root, List<Integer> result) {if (root == null) {return;}result.add(root.val);preorder(root.left, result);preorder(root.right, result);}
}
// 中序遍历·递归·LC94_二叉树的中序遍历
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();inorder(root, res);return res;}void inorder(TreeNode root, List<Integer> list) {if (root == null) {return;}inorder(root.left, list);list.add(root.val);             // 注意这一句inorder(root.right, list);}
}
// 后序遍历·递归·LC145_二叉树的后序遍历
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();postorder(root, res);return res;}void postorder(TreeNode root, List<Integer> list) {if (root == null) {return;}postorder(root.left, list);postorder(root.right, list);list.add(root.val);             // 注意这一句}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_925934.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

NFS的介绍与管理

NFS 文章目录 NFS1. nfs简介1.1 nfs特点1.2 nfs的应用场景1.3 nfs的体系组成 2. nfs工作机制2.1 RPC2.2 nfs工作机制 3. exports文件的格式4. nfs管理 1. nfs简介 1.1 nfs特点 NFS&#xff08;Network File System&#xff09;即网络文件系统&#xff0c;是FreeBSD支持的文件…

Defi安全--Zunami Protocol攻击事件分析

其它相关内容可见个人主页 1 Zunami攻击事件相关信息 2023.8.13发生在Ethereum上发生的攻击&#xff0c;存在两个攻击交易&#xff0c;具体信息如下&#xff1a; 攻击合约地址&#xff1a;Contract Address 攻击合约 攻击者地址&#xff1a;Zunami Protocol Exploiter 攻击…

vivado Revision Control

2020.2 只需要git 管理 prj.xpr 和 prj.srcs/ https://china.xilinx.com/video/hardware/ip-revision-control.html Using Vivado Design Suite with Revision Control https://www.xilinx.com/video/hardware/vivado-design-suite-revision-control.html http://www.xi…

《PCI Express体系结构导读》随记 —— 第I篇 第2章 PCI总线的桥与配置(16)

接前一篇文章&#xff1a;《PCI Express体系结构导读》随记 —— 第I篇 第2章 PCI总线的桥与配置&#xff08;15&#xff09; 2.3.2 PCI Agent设备的配置空间 在PCI Agent设备的配置空间中包含了许多寄存器&#xff0c;这些寄存器决定了该设备在PCI总线中的使用方法&#xff0…

Shiro漏洞

VULHUB部署环境 下载vulhub https://github.com/vulhub/vulhub/archive/master.zip?spma2c6h.12873639.article-detail.7.76036a98Plc8q5&filemaster.zip 进入漏洞文件夹直接部署 界面 漏洞 如果勾选记住账号&#xff0c;请求包会附带remember-me字段&#xff0c;服务…

MetaGPT入门(一)

本文在Win11操作系统下进行&#xff0c;工具pycharm 一、环境准备 1.建议使用conda虚拟环境 安装anaconda参考&#xff1a;Windows10下Anaconda的安装_windows anaconda 路径-CSDN博客 打开Anaconda Powershell Prompt命令窗口&#xff0c;输入下面命令&#xff0c;创建3.1…

专业课145+合肥工业大学833信号分析与处理考研经验合工大电子信息通信

今年专业课145也是考研科目中最满意的一门&#xff0c;其他基本相对平平&#xff0c;所以这里我总结一下自己的专业课合肥工业大学833信号分析与处理的复习经验。 我所用的教材是郑君里的《信号与系统》&#xff08;第三版&#xff09;和高西全、丁玉美的《数字信号处理》&…

Qt超简单实现贪吃蛇

文章目录 常量Snake类GameController类GUI显示游戏简图 为了能够最简单地完成程序&#xff0c;所以没有用类的继承等知识。感兴趣的朋友可以改写一下。 常量 const int FILE_SIZE 30; //地图方格大小 const int FPS 5000 / 33; //游戏运行帧率 enum Item{empty, wall, food…

1.环境部署

1.虚拟机安装redhat8系统 这个其实很简单&#xff0c;但是有一点小细节需要注意。 因为我的电脑是 16核心的&#xff0c;所以选择内核16&#xff0c;可以最大发挥虚拟机的性能 磁盘选择SATA&#xff0c;便于后期学习 将一些没用的设备移除 选择安装redhat 8 时间选择上海 选择…

jdbc-mysql

NotWritablePropertyException: Invalid property driverClass of beanclass (com.alibabadruid.pool.DruidDataSource] Bean property "driverClass mysql的配置有问题

web练习2

需求 1.计算用户指定的数值内的奇数和。例如用户输入的是10则计算13579的和 <!doctype html> <html lang"en"> <head><meta charset"utf-8"><title>作业1</title></head> <body> <script>//计算用…

黄金t+d与黄金期货交易的区别

在金融投资领域中&#xff0c;黄金是一种重要的避险工具和财富保值增值手段。对于投资者来说&#xff0c;了解并熟悉不同的黄金交易方式是至关重要的。其中&#xff0c;黄金TD和黄金期货交易是两种常见的黄金交易形式。那么&#xff0c;它们之间具体有哪些区别呢&#xff1f; 了…

光鉴科技的反卷思维,让科技不再难做

文 | 智能相对论 作者 | 陈壹 中国企业的全球竞争力&#xff0c;正从“拼人力、拼产能”转为“拼技术、拼创新”的新阶段。据世界知识产权组织发布的《世界知识产权指标报告》显示&#xff0c;2022年中国专利申请量约160万件&#xff0c;排名世界第一。而在最近发布的全球百强…

使用 Picocli 开发 Java 命令行,5 分钟上手

大家好&#xff0c;我是鱼皮&#xff0c;对不会前端的同学来说&#xff0c;开发 命令行工具 是一种不错的展示系统功能的方式。在 Java 中开发命令行工具也很简单&#xff0c;使用框架&#xff0c;几分钟就能学会啦~ Picocli 入门 Picocli 是 Java 中个人认为功能最完善、最简单…

1.机器学习-机器学习算法分类概述

机器学习-机器学习算法分类概述 个人简介机器学习算法分类&#xff1a;监督学习、无监督学习、强化学习一监督学习1. 监督学习分类任务举例&#xff1a;1.1 特征1.2 标签 二无监督学习1.关键特点2.应用示例3.常见的无监督学习算法 三强化学习1.定义2.示例场景 四机器学习开发流…

【搜索引擎设计:信息搜索怎么避免大海捞针?

在前面我们提到了网页爬虫设计&#xff1a;如何下载千亿级网页&#xff1f;中&#xff0c;我们讨论了大型分布式网络爬虫的架构设计&#xff0c;但是网络爬虫只是从互联网获取信息&#xff0c;海量的互联网信息如何呈现给用户&#xff0c;还需要使用搜索引擎完成。因此&#xf…

Flutter-Web从0到部署上线(实践+埋坑)

本文字数&#xff1a;7743字 预计阅读时间&#xff1a;60分钟 01 前言 首先说明一下&#xff0c;这篇文章是给具备Flutter开发经验的客户端同学看的。Flutter 的诞生虽然来自 Google 的 Chrome 团队&#xff0c;但大家都知道 Flutter 最先支持的平台是 Android 和 iOS&#xff…

c语言-数据类型(下)

目录 4.实型变量 5.字符常量 直接常量&#xff1a; 转义字符&#xff1a; 6.字符变量 7.字符串常量 五、输出格式总结 整型&#xff1a; 浮点型&#xff1a; 字符及字符串&#xff1a; 指针&#xff08;地址&#xff09;&#xff1a; 六、typedef 七、sizeof一个问…

鸿蒙开发之blank组件

一、使用 使用blank可以在row/column/flex在容器主轴方向上填充剩余部分。 可以通过设置min最小宽度/高度来控制填充的大小&#xff0c; 也可以通过backgroundColor设置背景颜色来改变默认的透明色填充。 //设置最小宽度为200&#xff0c;填充颜色灰色 Blank(200).backgrou…

项目架构之Zabbix部署

1 项目架构 1.1 项目架构的组成 业务架构&#xff1a;客户端 → 防火墙 → 负载均衡&#xff08;四层、七层&#xff09; → web缓存/应用 → 业务逻辑&#xff08;动态应用&#xff09; → 数据缓存 → 数据持久层 运维架构&#xff1a;运维客户端 → 跳板机/堡垒机&#x…