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

二叉树的这五种遍历方法你们都会了吗?

说在前面

🎈二叉树大家应该都很熟了吧,那二叉树的这五种遍历方式你们都会了吗?

以这一二叉树为例子,我们来看看不同遍历方式返回的结果都是怎样的。

前序遍历

前序遍历的顺序是:首先访问根节点,然后递归地遍历左子树,最后递归地遍历右子树。

var preorderTraversal = function(root) {const res = [];const traversal = (r)=>{if (r === null) return;res.push(r.val); // 访问根节点traversal(r.left); // 遍历左子树traversal(r.right); // 遍历右子树};traversal(root);return res;
};
  • 输出结果
[3,9,20,15,7]

中序遍历

中序遍历的顺序是:首先递归地遍历左子树,然后访问根节点,最后递归地遍历右子树。

var inorderTraversal = function(root) {const res = [];const traversal = (r)=>{if (r === null) return;traversal(r.left); // 遍历左子树res.push(r.val); // 访问根节点traversal(r.right); // 遍历右子树};traversal(root);return res;
};
  • 输出结果
[9,3,15,20,7]

后序遍历

后序遍历的顺序是:首先递归地遍历左子树,然后递归地遍历右子树,最后访问根节点。

var postorderTraversal = function(root) {const res = [];const traversal = (r)=>{if (r === null) return;traversal(r.left); // 遍历左子树traversal(r.right); // 遍历右子树res.push(r.val); // 访问根节点};traversal(root);return res;
};
  • 输出结果
[9,15,7,20,3]

层序遍历

层序遍历按照从上到下、从左到右的顺序访问二叉树的所有节点。

以广度优先策略遍历节点的方法:

  • 使用队列作为辅助数据结构。
  • 按照节点的深度层次访问二叉树,从根节点开始,逐层向下。
var levelOrderTraversal = function(root) {const res = [];const queue = [root];if(!root) return [];while(queue.length > 0){const node = queue.shift();res.push(node.val);node.left && queue.push(node.left);node.right && queue.push(node.right);}return res;
};
  • 输出结果
[3,9,20,15,7]

垂序遍历

对位于 (row, col) 的每个结点而言,其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0) 。

二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束,按列索引每一列上的所有结点,形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点,则按结点的值从小到大进行排序。

在层序遍历的基础上记录每个数据所在的位置再重新进行排序即可。

var verticalTraversal = function (root) {const nodeList = [];const q = [{ node: root, row: 0, col: 0 }];//获取二叉树节点集合while (q.length) {const { node, row, col } = q.shift();nodeList.push({ val: node.val, row: row, col });if (node.left) q.push({ node: node.left, row: row - 1, col: col + 1 });if (node.right) q.push({ node: node.right, row: row + 1, col: col + 1 });}//对二叉树节点进行排序nodeList.sort((a, b) => {if (a.row === b.row && a.col === b.col) {return a.val - b.val;}return a.row - b.row;});//对二叉树节点进行分组const res = [[nodeList[0].val]];for (let i = 1; i < nodeList.length; i++) {if (nodeList[i].row !== nodeList[i - 1].row) {res.push([]);}res[res.length - 1].push(nodeList[i].val);}return res;
};
  • 输出结果
[[9],[3,15],[20],[7]]

公众号

关注公众号『前端也能这么有趣』,获取更多有趣内容。

说在后面

🎉 这里是 JYeontu,现在是一名前端工程师,有空会刷刷算法题,平时喜欢打羽毛球 🏸 ,平时也喜欢写些东西,既为自己记录 📋,也希望可以对大家有那么一丢丢的帮助,写的不好望多多谅解 🙇,写错的地方望指出,定会认真改进 😊,偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章,有兴趣的也可以关注下。在此谢谢大家的支持,我们下文再见 🙌。

相关文章:

二叉树的这五种遍历方法你们都会了吗?

说在前面 &#x1f388;二叉树大家应该都很熟了吧&#xff0c;那二叉树的这五种遍历方式你们都会了吗&#xff1f; 以这一二叉树为例子&#xff0c;我们来看看不同遍历方式返回的结果都是怎样的。 前序遍历 前序遍历的顺序是&#xff1a;首先访问根节点&#xff0c;然后递归地…...

使用模数转换器的比例电阻测量基础知识

A/D 转换器是比率式的&#xff0c;也就是说&#xff0c;它们的结果与输入电压与参考电压的比值成正比。这可用于简化电阻测量。 测量电阻的标准方法是让电流通过电阻并测量其压降 &#xff08;见图 1&#xff09;。然后&#xff0c;欧姆定律(V I x R) 可用于计算电压和电流的…...

(C++语言的设计和演化) C++的设计理念

文章目录 前言&#x1f4d6;C 语言设计规则&#x1f4d0;规则和原理&#x1f4d0;一般性规则&#x1f4d0;设计支持规则&#x1f4d0;语言的技术性规则&#x1f4d0;低级程序设计支持规则 &#x1f4d6;标准化&#xff08;扩充评判准则&#xff09;&#x1f4d0;它精确吗&#…...

AI音乐:创新引擎还是创意终结者?

✨作者主页&#xff1a; Mr.Zwq✔️个人简介&#xff1a;一个正在努力学技术的Python领域创作者&#xff0c;擅长爬虫&#xff0c;逆向&#xff0c;全栈方向&#xff0c;专注基础和实战分享&#xff0c;欢迎咨询&#xff01; 您的点赞、关注、收藏、评论&#xff0c;是对我最大…...

20240621每日后端---------如何优化项目中的10000个if-else 语句?

如何优化 10000 个 if-else 语句&#xff1f;有没有好的解决方案&#xff1f; 额&#xff0c;本身问题就很奇怪&#xff0c;怎么可能有这种代码。。。世界你让我陌生&#xff0c;但是我们还是假象着看看能不能解决一下。 解决方案1&#xff1a;策略模式 使用策略模式确实可以…...

【STM32】时钟树系统

1.时钟树简介 1.1五个时钟源 LSI是低速内部时钟&#xff0c;RC振荡器&#xff0c;频率为32kHz左右。供独立看门狗和自动唤醒单元使用。 LSE是低速外部时钟&#xff0c;接频率为32.768kHz的石英晶体。这个主要是RTC的时钟源。 HSE是高速外部时钟&#xff0c;可接石英*/陶瓷谐振…...

docker换源

文章目录 前言1. 查找可用的镜像源2. 配置 Docker 镜像源3. 重启 Docker 服务4. 查看dock info是否修改成功5. 验证镜像源是否更换成功注意事项 前言 在pull镜像时遇到如下报错&#xff1a; ┌──(root㉿kali)-[/home/longl] └─# docker pull hello-world Using default …...

百度在线分销商城小程序源码系统 分销+会员组+新用户福利 前后端分离 带完整的安装代码包以及搭建部署教程

系统概述 百度在线分销商城小程序源码系统是一款集分销、会员组管理和新用户福利于一体的前后端分离的系统。它采用先进的技术架构&#xff0c;确保系统的稳定性、高效性和安全性。该系统的前端基于小程序开发&#xff0c;为用户提供了便捷的购物体验和交互界面。用户可以通过…...

Flutter【组件】富文本组件

简介 flutter 富文本组件。 github地址&#xff1a; https://github.com/ThinkerJack/jac_uikit pub地址&#xff1a;https://pub.dev/packages/jac_uikit 使用方式 运行 flutter pub add jac_uikit组件文档 使用方式&#xff1a; HighlightedTextWidget.builder(text: &…...

中国恋爱交友相亲软件有哪些?大型婚恋相亲交友APP真实测评推荐

嘿嘿&#xff0c;当了29年的单身汪&#xff0c;这下总算不再单着啦&#xff01;这两年把身边能找的人都找遍了&#xff0c;也没碰到合适的。没办法&#xff0c;就跑到网上去试试&#xff0c;坚持了有半年&#xff0c;可算有对象啦&#xff01;下面给大家说说我用过的几个能脱单…...

快速欧氏聚类与普通欧氏聚类比较

1、前言 文献《FEC: Fast Euclidean Clustering for Point Cloud Segmentation》介绍了一种快速欧氏聚类方法,大概原理可以参考如下图,具体原理可以参考参考文献。 2、时间效率比较:快速欧氏聚类VS普通欧氏聚类 网上搜集的快速欧式聚类,与自己手写的普通欧式聚类进行对比,…...

如何让大语言模型在规格普通的硬件上运行 - 量化技术

近年来&#xff0c;大型语言模型&#xff08;LLMs&#xff09;的能力有了飞跃式的发展&#xff0c;使其在越来越多的应用场景中更加友好和适用。然而&#xff0c;随着LLMs的智能和复杂度的增加&#xff0c;其参数数量&#xff0c;即权重和激活值的数量也在增加&#xff0c;这意…...

shell printf详解

默认的 printf 不会像 echo 自动添加换行符&#xff0c;我们可以手动添加 \n。 1. printf命令语法组成&#xff1a; printg format-string [arguments] 第一部分为格式化字符串&#xff0c;该字符串最好用引号括起来 第二部分为参数列表,例如字符串或变量值的列表,该列表需…...

【数据分析】用Python做事件抽取任务-快速上手方案

目录 方法一&#xff1a;使用OmniEvent库安装OmniEvent使用OmniEvent进行事件抽取OmniEvent优点缺点 方法二&#xff1a;使用大模型使用GPT网页版进行事件抽取事件类型列表 大模型优点缺点 总结 在自然语言处理&#xff08;NLP&#xff09;领域&#xff0c;事件抽取是一项关键任…...

B端系统门门清之:HRM,人力资源系统,公司发展的源动力。

人才是公司发展的源动力&#xff0c;针对公司复杂人力的管理就是HRM系统的核心功能&#xff0c;本文就带领大家详细认识一下HRM系统&#xff0c;分别从什么是HRM系统&#xff0c;作用、功能模块、颜值提升四个方面来阐述。欢迎大家点赞评论收藏转发。 一、什么是HRM系统 HRM系…...

tplink安防监控raw文件转码合成mp4的方法

Tplink(深圳普联)专业的网络设备生产商&#xff0c;属于安防监控市场的后来者。Tplink的安防产品恢复了很多&#xff0c;其嵌入式文件系统也一直迭代更新。今天要说的案例比较特殊&#xff0c;其不仅仅要求恢复&#xff0c;还要求能解析出音频并且要求画面和声音实现“同步”。…...

每天一个数据分析题(三百八十三)- 聚类

关于忽略自相关可以带来什么问题描述错误的是&#xff1f; A. 均方误差可能严重低估误差项的方差 B. 可能导致高估检验统计量t值&#xff0c;致使本不显著的变量变得显著了 C. 参数估计值的最小方差无偏性不再成立 D. 参数估计值的最小方差无偏性仍成立 数据分析认证考试介…...

构建下一代数据解决方案:SingleStore、MinIO 和现代 Datalake 堆栈

SingleStore 是专为数据密集型工作负载而设计的云原生数据库。它是一个分布式关系 SQL 数据库管理系统&#xff0c;支持 ANSI SQL&#xff0c;并因其在数据引入、事务处理和查询处理方面的速度而受到认可。SingleStore 可以存储关系、JSON、图形和时间序列数据&#xff0c;以满…...

【经验分享】Ubuntu24.04安装微信

【经验分享】Ubuntu24.04安装微信(linux官方2024universal版) 文章如下&#xff0c;22.04和24.04微信兼容 【经验分享】Ubuntu22.04安装微信(linux官方2024universal版) 实测Ubuntu24.04LTS版本可以兼容。...

AXI学习笔记

文章目录 AXI口诀&#xff1a;AXI三种总线&#xff0c;三种接口&#xff0c;一个协议背景知识一、 AMBA&#xff1a;二、AXI2.1 通信协议与握手机制2.2 AXI协议特点2.3 三种AXI总线类型&#xff08;AXI4、AXI4-lite、AXI4-stream&#xff09;2.3.1 AXI通道&#xff08;5通道&am…...

Spring boot 启动报:Do not use @ for indentation

一、使用maven插件动态切换配置时出现报错 二、配置文件及pom 2.1 配置文件结构 2.2 application.yml spring: # 根据环境读取配置文件&#xff08;手动&#xff09; # profiles: # active: dev# 根据环境读取配置文件&#xff08;通过勾选maven插件&#xff09;profiles…...

【数据结构】排序(下)

个人主页~ 排序&#xff08;上&#xff09; 栈和队列 排序 二、常见排序的实现8、快速排序的优化9、非递归快速排序&#xff08;1&#xff09;基本思想&#xff08;2&#xff09;代码实现&#xff08;3&#xff09;时间复杂度&#xff08;4&#xff09;空间复杂度 10、归并排序…...

基于Java+Swing贪吃蛇小游戏(含课程报告)

博主介绍&#xff1a; 大家好&#xff0c;本人精通Java、Python、C#、C、C编程语言&#xff0c;同时也熟练掌握微信小程序、Php和Android等技术&#xff0c;能够为大家提供全方位的技术支持和交流。 我有丰富的成品Java、Python、C#毕设项目经验&#xff0c;能够为学生提供各类…...

三角形法恢复空间点深度

三角形法恢复空间点深度 如下图&#xff0c;以图 I 1 I_1 I1​为参考&#xff0c;图 I 2 I_2 I2​的变换矩阵为 T T T。相机光心为 O 1 O_1 O1​和 O 2 O_2 O2​。在图 I 1 I_1 I1​中有特征点 p 1 p_1 p1​&#xff0c;对应图 I 2 I_2 I2​中有特征点 p 2 p_2 p2​。理论上直…...

Linux 阻塞和非阻塞 IO 实验学习

Linux 阻塞和非阻塞 IO 实验学习 IO 指的是 Input/Output&#xff0c;也就是输入/输出&#xff0c;是应用程序对驱动设备的输入/输出操作。当应用程序对设备驱动进行操作的时候&#xff0c;如果不能获取到设备资源&#xff0c;那么阻塞式 IO 就会将应用程序对应的线程挂起&…...

JuiceFS 社区版 v1.2 发布,新增企业级权限管理、平滑升级功能

JuiceFS 社区版 v1.2 今天正式发布&#xff0c;这是自 2021 年开源以来的第三个大版本。v1.2 也是一个长期支持版本&#xff08;LTS&#xff09;。我们将持续维护 v1.2 以及 v1.1 这两个版本&#xff0c;v1.0 将停止更新。 JuiceFS 是为云环境设计的分布式文件系统&#xff0c;…...

虚拟3D沉浸式展会编辑平台降低了线上办展的门槛

在数字化浪潮的引领下&#xff0c;VR虚拟网上展会正逐渐成为企业展示品牌实力、吸引潜在客户的首选平台。我们与广交会携手走过三年多的时光&#xff0c;凭借优质的服务和丰富的经验&#xff0c;赢得了客户的广泛赞誉。 面对传统展会活动繁多、企业运营繁忙的挑战&#xff0c;许…...

泛微E9开发 查询页面添加按钮,完成特定功能

查询页面添加按钮&#xff0c;完成特定功能 1、关联知识&#xff08;查询页面实现新增按钮&#xff09;2、功能实现2.1. 点击按钮&#xff0c;输出选中的checkbox的值2.2. 点击按钮&#xff0c;打开一个自定义对话框 3、实现方法 1、关联知识&#xff08;查询页面实现新增按钮&…...

初学51单片机之数字秒表

不同数据类型间的相互转换 在C语言中&#xff0c;不同数据类型之间是可以混合运算的。当表达式中的数据类型不一致时&#xff0c;首先转换为同一类型&#xff0c;然后再进行计算。C语言有两种方式实现类型转换。一是自动类型转换&#xff0c;另外一种是强制类型转换。 转换的主…...

SpringBoot整合justauth实现多种方式的第三方登陆

目录 0.准备工作 1.引入依赖 2.yml文件 3. Controller代码 4.效果 参考 0.准备工作 你需要获取三方登陆的client-id和client-secret 以github为例 申请地址&#xff1a;Sign in to GitHub GitHub 1.引入依赖 <?xml version"1.0" encoding"UTF-8&quo…...

企业网站推广方式和策略/专业软文发布平台

宁波市第23届中小学生计算机程序设计竞赛复赛试题(小学组)宁波市第2届中小学生计算机程序设计竞赛复赛试题(小学组)题目一览试题名称 排名导游奖品英文代号 paimingdaoyoujiangpin程序名 .pas/c/cpp paiming.pas/c/cpp daoyou.pas/c/cpp jiangpin.pas/c/cpp 输入文件名 .in pai…...

外国网站备案/软文营销的作用

移动应用程序是每个人生活的重要组成部分&#xff0c;人们可以使用手机应用程序做任何事情。创建最好的应用程序需要更好的技术&#xff0c;Java移动应用程序开发是一种流行的选择&#xff0c;企业为功能丰富的Android应用程序雇佣Java程序员。 首先&#xff0c;Java开发服务对…...

做算命网站挣钱吗/seo网站建设公司

2019独角兽企业重金招聘Python工程师标准>>> 在少数需求下&#xff0c;需要能够自动打包&#xff0c;将app发布到不同的平台&#xff0c;那么下面给出本人使用的自动打包脚本: # 以下内容到分割线是&#xff0c;需要针对每个项目进行配置的部分 buildDay$(date %Y%m…...

2008 iis7添加网站/惠州seo排名

官方文档地址&#xff1a;https://github.com/axios/axios axios 是一个基于 Promise 的HTTP库&#xff0c;可以用在浏览器和 node.js 中 特性&#xff1a; • 从浏览器发起 XMLHttpRequests 请求 • 从 node.js 发起 http 请求 • 支持 Promise API • 拦截请求和响应 • 转换…...

阅读转发网站那些做的比较好/天津网站快速排名提升

板子&#xff0c;全是板子 该模板目前行数&#xff08;Markdown下包括文字&#xff09;&#xff1a;4799 行 更新日志&#xff08;从2018.11.19开始&#xff09; 2019.04.05 : 更新了数据结构->左偏树 2019.04.02 : 更新了数据结构->平衡树->WBLT 2019.03.26 : 更新了…...

外贸网站做流量/武汉网站推广公司

这篇文章主要为大家详细介绍了python忽略警告(warning) 错误实现方法&#xff0c;具有一定的参考价值&#xff0c;可以用来参考一下。对python这个高级语言感兴趣的小伙伴&#xff0c;下面一起跟随512笔记的小编两巴掌来看看吧&#xff01;运行一个python文件&#xff0c;一直报…...