二叉树的层序遍历

loser

27 Aug 2026 • 6 min read

给你二叉树的根节点 root，返回其节点值的层序遍历结果。

层序遍历就是逐层地、从左到右访问所有节点。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

队列（层序遍历）：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;

        if (root == nullptr)
        {
            return ans;
        }

        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty())
        {
            int size = q.size();
            vector<int> level;

            for (int i = 0; i < size; i++)
            {
                TreeNode* node = q.front();
                q.pop();

                level.push_back(node->val);

                if (node->left != nullptr)
                {
                    q.push(node->left);
                }

                if (node->right != nullptr)
                {
                    q.push(node->right);
                }
            }

            ans.push_back(level);
        }

        return ans;
    }
};

核心思想

层序遍历要求按照：

第 1 层 -> 第 2 层 -> 第 3 层 -> ...

的顺序访问节点，并且每一层内部从左到右访问。

队列具有先进先出的特点。

把根节点放进队列后，先出队的一定是当前层更靠左的节点。

处理当前节点时，再把它的左孩子和右孩子依次加入队列。

这样下一层节点会按照从左到右的顺序排在队列后面。

这题最关键的观察是：

每轮循环开始时，队列中已有的节点恰好属于当前这一层。

因此，先记录当前队列大小 size，再连续处理 size 个节点，就能把这一层的节点值收集到同一个数组中。

队列中存什么

队列中保存还没有访问的树节点：

queue<TreeNode*> q;

初始时，根节点是第 1 层唯一的节点：

q.push(root);

之后处理任意一个节点时：

先访问当前节点
再把左孩子加入队列
最后把右孩子加入队列

因为左孩子先入队，所以同一层中它也会先被访问。

这就保证了从左到右的顺序。

如何区分每一层

如果只是不停地从队列中取节点，确实可以遍历整棵树。

但题目要求返回：

[[第 1 层], [第 2 层], [第 3 层], ...]

所以必须知道哪些节点属于同一层。

在每一轮开始时：

int size = q.size();

此时队列中的这 size 个节点，正好是当前层的全部节点。

接下来的循环只处理这 size 个节点：

for (int i = 0; i < size; i++)

在处理过程中加入队列的孩子节点，都属于下一层。

因此它们不会在当前轮被处理，而会留到下一轮。

层序遍历过程

每一层都执行相同的过程：

记录当前层节点数量 size。
创建数组 level 保存当前层的节点值。
连续出队 size 次，把节点值加入 level。
把当前节点的非空左右孩子按顺序入队。
把 level 加入答案 ans。

代码中的核心部分是：

int size = q.size();
vector<int> level;

for (int i = 0; i < size; i++)
{
    TreeNode* node = q.front();
    q.pop();

    level.push_back(node->val);

    if (node->left != nullptr)
    {
        q.push(node->left);
    }

    if (node->right != nullptr)
    {
        q.push(node->right);
    }
}

ans.push_back(level);

为什么孩子节点不会混入当前层

当前轮开始时，size 已经固定为当前层节点数量。

即使处理当前层节点时，把它们的孩子加入了队列，for 循环也只会执行 size 次。

所以新加入的孩子节点不会在当前轮出队。

它们会留在队列中，成为下一轮要处理的节点。

这正是按层分组的关键。

边界情况

如果二叉树为空：

root = []

没有任何节点，也没有任何层。

直接返回空数组：

[]

如果二叉树只有一个节点：

root = [1]

队列中只有根节点，第一轮处理后得到：

[[1]]

如果树退化成一条链，每一层只有一个节点，答案中每个数组只包含一个值。

正确性证明

我们证明：算法能按从上到下、从左到右的顺序，正确返回二叉树每一层的节点值。

结论 1：队列中的节点始终按层从左到右排列

初始时，队列只有根节点，结论成立。

假设当前层节点已经按从左到右顺序在队列中排列。

算法按队列顺序依次取出这些节点。

对于每个节点，先将左孩子入队，再将右孩子入队。

因此下一层节点会按照“父节点从左到右，且每个父节点的左孩子在右孩子之前”的顺序入队。

这正好是下一层从左到右的顺序。

所以队列中的节点始终按层从左到右排列。

结论 2：每轮循环恰好处理一层节点

每轮开始时，size = q.size()，队列中的全部节点都是当前层节点。

循环固定执行 size 次，因此每个当前层节点都会被处理一次。

处理过程中加入队列的节点都是当前层节点的孩子，属于下一层。

由于循环次数已经固定，它们不会在当前轮被处理。

所以每轮循环恰好处理一层节点。

结论 3：每个节点都会被访问一次且不会重复

根节点在开始时入队一次。

每个非根节点只会在它的父节点被处理时入队一次。

队列中的节点都会在某一轮出队并加入对应层结果。

因此每个节点都会被访问一次，且不会重复访问。

得出结论

由结论 1 可知，节点在每一层内按照从左到右顺序访问。

由结论 2 可知，算法能正确区分每一层。

由结论 3 可知，所有节点都会被完整且不重复地加入结果。

因此算法返回的 ans 就是二叉树正确的层序遍历结果。

举例理解

以：

root = [3,9,20,null,null,15,7]

为例，这棵树可以表示为：

遍历过程如下：

当前轮	队列开始状态	收集的 `level`	下一轮队列
第 1 层	`[3]`	`[3]`	`[9,20]`
第 2 层	`[9,20]`	`[9,20]`	`[15,7]`
第 3 层	`[15,7]`	`[15,7]`	`[]`

最终结果是：

[[3],[9,20],[15,7]]

复杂度分析

设二叉树节点数为 n，树的最大宽度为 w。

每个节点都会入队一次、出队一次。

时间复杂度：O(n)
空间复杂度：O(w)

队列最多同时保存某一层的节点，因此最坏情况下 w 可以达到 O(n)。

返回结果 ans 不计入额外空间。