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

二叉树的层序遍历

给你二叉树的根节点 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; // 返回层序遍历的结果
};

讲解

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

循环

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; // 返回层序遍历的结果
}

讲解

1. 当前层初始化：使用一个数组 currentLevel 来存储当前层的节点，初始时将根节点放入该数组。
2. 循环访问：当 currentLevel 不为空时，循环进行以下操作：
   • 创建一个新的数组 nextLevel 用于存储下一层的节点。
   • 创建一个数组 currentValues 用于存储当前层的节点值。
3. 遍历当前层：使用一个 for 循环遍历 currentLevel 中的节点：
   • 记录节点值到 currentValues。
   • 如果节点有左子节点或右子节点，则将它们加入 nextLevel。
4. 结果存储：将 currentValues 加入到 result 中。
5. 更新当前层：清空 currentLevel，并将 nextLevel 中的节点加入 currentLevel。
6. 返回结果：最终返回层序遍历的结果数组。

总结

任重而道远！