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

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

article 2024/10/2 21:47:06

文章目录

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

二叉树的层序遍历

给你二叉树的根节点 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。
返回结果：最终返回层序遍历的结果数组。