XingHuiSama の博客

给你二叉树的根节点 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

‍
‍

使用迭代的方式写

‍

1. 算法核心思想：广度优先搜索（BFS）与队列

如果说“深度优先搜索（DFS）”是一个探险家一条路走到黑；那么“广度优先搜索（BFS）”就像是水波纹的扩散，一层一层地向外辐射。

要实现这种“一层一层”的访问，我们需要一个符合**“先进先出”（FIFO）特性的数据结构，也就是队列（Queue）。

每一层的节点按照从左到右的顺序排队进入队列。
队列前面的老节点出队（被访问）时，顺便把它的左右孩子（下一层的新节点）拉进队伍的最后面。

‍
‍

2. 代码逻辑拆解

第一步：边界拦截与初始化 如果树为空（root == NULL），直接返回空的二维数组。否则，将根节点压入队列，并初始化第一层的节点数为 count = 1。 (注：代码中把判空放在了 push 后面，逻辑上没问题因为直接 return 了，但在工程习惯上，通常会把 if (root == NULL) 放在函数的第一行最先判断。)
第二步：按层处理（外层 while 循环） 只要队列不为空，说明树还没有遍历完。每一次 while 循环的执行，都代表着正在处理完整的一层。
第三步：固定当层人数（核心精髓！） 这是这道题最关键的一步。普通的 BFS 只需要一个 while 不断弹出一个节点即可。但本题要求把每一层分开打包进 vector<int> 中。你的做法非常聪明：在进入内层循环前，此时队列里的节点全都是同一层的节点。利用 count 固定住当前层的人数。
第四步：同层节点出队与拓展（内层 for 循环） 利用 for 循环，精确地让当前层的 count 个节点依次出队：
1. 获取队头节点，记录它的值到 temp。
2. 将队头节点 pop 出队。
3. 如果它有左/右孩子，就把孩子们排到队列末尾去。 (因为循环次数是被 count 锁死的，所以新排进队伍的孩子们绝不会在这一轮被错误地弹出，它们会乖乖等到下一轮 while 循环时再作为新的一层被处理。)
第五步：结算本层，准备下一层 内层循环结束后，把记录当前层节点值的 temp 数组塞入最终结果 ans 中。此时，上一层的老节点已经全部出队，队列里剩下的全都是刚刚加进来的下一层新节点。所以直接用 count = queue1.size(); 更新下一层的人数，继续循环。

‍
‍

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> queue1;
        queue1.push(root);
        vector<vector<int>> ans;
        if (root == NULL) {
            return ans;
        }

        int count = 1;
        while (queue1.size() > 0) {
            vector<int> temp;
            for (int i = 0;i < count;i++) {
                TreeNode* node = queue1.front();
                temp.push_back(node->val);

                queue1.pop();
                if (node->left != NULL) {
                    queue1.push(node->left);
                }
                if (node->right != NULL) {
                    queue1.push(node->right);
                }

            }

            ans.push_back(temp);
            count = queue1.size();
        }

        return ans;
    }
};

3. 复杂度分析

时间复杂度：O(N)。其中 N 是二叉树的节点数。每个节点都会被精确地进队一次、出队一次，并且处理时间为常数级别，整体时间开销与节点数量成正比。
空间复杂度：O(N)。空间开销主要取决于队列的最大长度。在最坏情况下（例如满二叉树的最后一层），队列中会同时包含大约 N/2 个节点，因此空间复杂度为线性的 O(N)。

‍