【代码随想录刷题总结】二叉树的层序遍历

引言

大家好啊，我是前端拿破轮😁。

跟着卡哥学算法有一段时间了，通过代码随想录的学习，受益匪浅，首先向卡哥致敬🫡。

但是在学习过程中我也发现了一些问题，很多当时理解了并且AC的题目过一段时间就又忘记了，或者不能完美的写出来。根据费曼学习法，光有输入的知识掌握的是不够牢靠的，所以我决定按照代码随想录的顺序，输出自己的刷题总结和思考。同时，由于以前学习过程使用的是JavaScript,而在2025年的今天，TypeScript几乎成了必备项，所以本专题内容也将使用TypeScript，来巩固自己的TypeScript语言能力。

题目信息

二叉树的层序遍历。

leetcode题目链接

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

题目分析

本题考察另一种二叉树的基本遍历操作——层序遍历。其实二叉树可以当做一种特殊的图。所以层序遍历就是广度优先遍历。同样需要使用队列来进行辅助遍历。

首先进行边界条件剪枝，如果根节点为null，直接返回空数组。

然后将根节点入队，并记录当前队列长度。每一层遍历过程中，在最开始都要先记录队列长度。因为我们在处理完一个节点后，如果该节点有左右孩子，就会将左右孩子入队。所以必须在遍历这一层最开始的时候记录本层节点数量，才能保证遍历不会越界。

在每一层的遍历中，要创建一个存放本层节点的数组。因为最后返回的层序遍历结果应该是一个二维数组。二维数组中的每一个一维数组表示一层的遍历结果。在每层遍历中将本层的节点加入本层数组。一层遍历结束时，将本层数组加入结果数组中。

最后，当队列为空时，说明所有节点遍历完成，返回结果数组即可。

题解

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function levelOrder(root: TreeNode | null): number[][] {
    // 结果数组
    const result: number[][] = [];

    // 剪枝
    if (!root) return result;

    // 辅助队列
    const queue: TreeNode[] = [];

    // 根节点入队
    queue.push(root);

    // 当队列非空时，开始遍历
    while (queue.length) {
        // 记录本层长度
        const len = queue.length;

        // 本层节点数组
        const current: number[] = [];

        // 遍历本层元素
        for (let i = 0; i < len; i++) {
            // 队头元素出队
            const q = queue.shift();

            // 将q的值加入本层节点数组
            current.push(q.val);

            // 如果有左右孩子，依次入队
            q.left && queue.push(q.left);
            q.right && queue.push(q.right);
        }
        // 将本层节点加入结果数组
        result.push(current);
    }
    // 返回结果数组
    return result;
};

时间复杂度：$O(n)$：每个节点只进队一次，出队一次，所以对每个节点只进行常数次操作。

空间复杂度：$O(n)$：结果数组是一个二维数组，包含所有节点，空间大小是$O(n)$，辅助队列最坏情况下有一整层节点，最多有（n / 2）个节点。

总结

本体考察对二叉树的基本遍历方式。层序遍历要利用队列来进行辅助。易错点是容易遍历越界，所以切记在每一层遍历开始之前，先保存本层的节点数。

好了，这篇文章就到这里啦，如果对您有所帮助，欢迎点赞,收藏,分享👍👍👍。您的认可是我更新的最大动力。由于笔者水平有限，难免有疏漏不足之处，欢迎各位大佬评论区指正。

往期推荐✨✨✨

• 面试官：二叉树的前中后序遍历，用递归和迭代分别实现🤓🤓🤓
• 腾讯面试官：听说你在字节面试用栈实现队列，那怎么用队列实现栈呢
• 字节面试官：用栈给我实现一个队列😏😏😏
• CJS和ESM两种模块化标准的异同分析
• 🤔5202年了，你不会还不知道WebAssembly吧？
• 🚀🚀🚀实在受不了混乱的提交——我使用了commitlint和commitizen
• 当我用deepwiki来学习React源码

我是前端拿破轮，关注我，一起学习前端知识，我们下期见！