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

学习记录：js算法（四十九）：二叉树的层序遍历

news 2025/6/28 19:29:28

文章目录

- 二叉树的层序遍历
- - 网上思路
  - - 队列
    - 循环
- 总结

二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的层序遍历。（即逐层地，从左到右访问所有节点）。

图一：
在这里插入图片描述

示例 1：如图一
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]示例 2：
输入：root = [1]
输出：[[1]]示例 3：
输入：root = []
输出：[]

我的思路
想使用数组的，但是没成功
网上思路
循环
队列

网上思路

队列

var levelOrder = function (root) {// 如果根节点为空，返回空数组if (!root) {return [];}const result = []; // 用于存储结果const queue = [root]; // 初始化队列，开始时将根节点入队while (queue.length > 0) {const levelSize = queue.length; // 当前层的节点数量const currentLevel = []; // 存储当前层的节点值for (let i = 0; i < levelSize; i++) {const node = queue.shift(); // 从队列中取出节点currentLevel.push(node.val); // 将节点值加入当前层的数组// 如果左子节点存在，入队if (node.left) {queue.push(node.left);}// 如果右子节点存在，入队if (node.right) {queue.push(node.right);}}// 将当前层的节点值数组加入结果数组result.push(currentLevel);}return result; // 返回层序遍历的结果
};

讲解

队列初始化：使用一个队列来存储待访问的节点，初始时将根节点入队。
循环访问：当队列不为空时，循环进行以下操作：
记录当前层的节点数量。
创建一个数组 currentLevel 用于存储当前层的节点值。
使用一个 for 循环遍历当前层的所有节点：
从队列中取出节点并记录其值。
如果该节点有左子节点或右子节点，则将它们入队。

结果存储：将当前层的节点值数组加入到结果数组 result 中。
返回结果：最终返回层序遍历的结果数组。

循环

var levelOrder = function (root) {// 如果根节点为空，返回空数组if (!root) {return [];}const result = []; // 用于存储结果const currentLevel = [root]; // 初始化当前层的节点数组while (currentLevel.length > 0) {const nextLevel = []; // 用于存储下一层的节点const currentValues = []; // 存储当前层的节点值// 遍历当前层的所有节点for (let i = 0; i < currentLevel.length; i++) {const node = currentLevel[i]; // 获取当前节点currentValues.push(node.val); // 记录节点值// 如果左子节点存在，加入下一层if (node.left) {nextLevel.push(node.left);}// 如果右子节点存在，加入下一层if (node.right) {nextLevel.push(node.right);}}// 将当前层的节点值加入结果数组result.push(currentValues);// 更新当前层为下一层currentLevel.length = 0; // 清空当前层currentLevel.push(...nextLevel); // 将下一层的节点加入当前层}return result; // 返回层序遍历的结果
}

讲解

当前层初始化：使用一个数组 currentLevel 来存储当前层的节点，初始时将根节点放入该数组。
循环访问：当 currentLevel 不为空时，循环进行以下操作：
创建一个新的数组 nextLevel 用于存储下一层的节点。
创建一个数组 currentValues 用于存储当前层的节点值。

遍历当前层：使用一个 for 循环遍历 currentLevel 中的节点：
记录节点值到 currentValues。
如果节点有左子节点或右子节点，则将它们加入 nextLevel。

结果存储：将 currentValues 加入到 result 中。
更新当前层：清空 currentLevel，并将 nextLevel 中的节点加入 currentLevel。
返回结果：最终返回层序遍历的结果数组。