Level Order

102. 二叉树的层序遍历

分析

初始化结果数组 res 和队列 q
若 root 为空，直接返回空的 res
将根节点加入队列，进入循环：
- 获取当前层节点数量 len
- 遍历当前层的所有节点：
  - 弹出队头节点，加入当前层结果数组 level
  - 将该节点的左右子节点（若存在）加入队列
- 将当前层的结果 level 加入到 res 中

时间复杂度

时间复杂度 O(n)，其中 n 是二叉树的节点总数。每个节点都会被访问一次

空间复杂度

空间复杂度 O(m)，其中 m 是二叉树的最大宽度。队列在最宽的层存储所有节点

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


class Solution
{
public:
    vector<vector<int>> levelOrder(TreeNode* root)
    {
        // 存储最终结果
        std::vector<std::vector<int>> res;
        if (!root) return res; // 特殊情况：空树

        // 初始化队列
        std::queue<TreeNode*> q;
        q.push(root);

        // 遍历每一层
        while (!q.empty())
        {
            int len = q.size(); // 当前层节点数
            std::vector<int> level; // 存储当前层的节点值

            // 遍历当前层的节点
            while (len--)
            {
                TreeNode* node = q.front();
                q.pop();
                level.push_back(node->val); // 将节点值加入当前层结果
                if (node->left) q.push(node->left); // 加入左子节点
                if (node->right) q.push(node->right); // 加入右子节点
            }
            res.push_back(level); // 将当前层结果加入到最终结果
        }

        return res; // 返回层序遍历结果
    }
};