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

2024-06-21 12:36

本文主要是介绍二叉树的这五种遍历方法你们都会了吗?,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

说在前面

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

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

前序遍历

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

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

这篇关于二叉树的这五种遍历方法你们都会了吗?的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

Python错误AttributeError: 'NoneType' object has no attribute问题的彻底解决方法

《Python错误AttributeError:NoneTypeobjecthasnoattribute问题的彻底解决方法》在Python项目开发和调试过程中,经常会碰到这样一个异常信息... 目录问题背景与概述错误解读:AttributeError: 'NoneType' object has no at

postgresql使用UUID函数的方法

《postgresql使用UUID函数的方法》本文给大家介绍postgresql使用UUID函数的方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录PostgreSQL有两种生成uuid的方法。可以先通过sql查看是否已安装扩展函数,和可以安装的扩展函数

Java中Arrays类和Collections类常用方法示例详解

《Java中Arrays类和Collections类常用方法示例详解》本文总结了Java中Arrays和Collections类的常用方法,涵盖数组填充、排序、搜索、复制、列表转换等操作,帮助开发者高... 目录Arrays.fill()相关用法Arrays.toString()Arrays.sort()A

Nginx安全防护的多种方法

《Nginx安全防护的多种方法》在生产环境中,需要隐藏Nginx的版本号,以避免泄漏Nginx的版本,使攻击者不能针对特定版本进行攻击,下面就来介绍一下Nginx安全防护的方法,感兴趣的可以了解一下... 目录核心安全配置1.编译安装 Nginx2.隐藏版本号3.限制危险请求方法4.请求限制(CC攻击防御)

python生成随机唯一id的几种实现方法

《python生成随机唯一id的几种实现方法》在Python中生成随机唯一ID有多种方法,根据不同的需求场景可以选择最适合的方案,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习... 目录方法 1:使用 UUID 模块(推荐)方法 2:使用 Secrets 模块(安全敏感场景)方法

MyBatis-Plus通用中等、大量数据分批查询和处理方法

《MyBatis-Plus通用中等、大量数据分批查询和处理方法》文章介绍MyBatis-Plus分页查询处理,通过函数式接口与Lambda表达式实现通用逻辑,方法抽象但功能强大,建议扩展分批处理及流式... 目录函数式接口获取分页数据接口数据处理接口通用逻辑工具类使用方法简单查询自定义查询方法总结函数式接口

MySQL深分页进行性能优化的常见方法

《MySQL深分页进行性能优化的常见方法》在Web应用中,分页查询是数据库操作中的常见需求,然而,在面对大型数据集时,深分页(deeppagination)却成为了性能优化的一个挑战,在本文中,我们将... 目录引言:深分页,真的只是“翻页慢”那么简单吗?一、背景介绍二、深分页的性能问题三、业务场景分析四、

JAVA中安装多个JDK的方法

《JAVA中安装多个JDK的方法》文章介绍了在Windows系统上安装多个JDK版本的方法,包括下载、安装路径修改、环境变量配置(JAVA_HOME和Path),并说明如何通过调整JAVA_HOME在... 首先去oracle官网下载好两个版本不同的jdk(需要登录Oracle账号,没有可以免费注册)下载完

Java中读取YAML文件配置信息常见问题及解决方法

《Java中读取YAML文件配置信息常见问题及解决方法》:本文主要介绍Java中读取YAML文件配置信息常见问题及解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要... 目录1 使用Spring Boot的@ConfigurationProperties2. 使用@Valu

Java 方法重载Overload常见误区及注意事项

《Java方法重载Overload常见误区及注意事项》Java方法重载允许同一类中同名方法通过参数类型、数量、顺序差异实现功能扩展,提升代码灵活性,核心条件为参数列表不同,不涉及返回类型、访问修饰符... 目录Java 方法重载(Overload)详解一、方法重载的核心条件二、构成方法重载的具体情况三、不构