LeetCode一百题—— 二叉树的层序遍历

有些算法题看起来很温和。

比如 LeetCode 102，二叉树的层序遍历。

它不像动态规划那样一上来就让人怀疑人生，也不像图论题那样名字里自带压迫感。题目只是说，给你一棵二叉树，请你按层把节点值收集起来。

听起来像一件很朴素的事。

第一层放一起，第二层放一起，第三层放一起。

但我觉得这题很适合放进 LeetCode 一百题里。它不只是考一段模板代码。它真正考的是，你有没有意识到，树不是只能从上到下一路递归着看，它也可以像一群排队的人一样，一层一层从眼前走过去。

这就是 BFS。

BFS 的中文常叫广度优先搜索。用更日常的话说，就是先看离你最近的一圈，再看下一圈，不急着往某一条路钻到底。

这题的手感，也正是从这里开始变清楚的。

一、题目真正想考什么

题目要求的是返回一个二维数组。

如果树长这样。

      3
     / \
    9  20
       / \
      15  7

那结果应该是这样。

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

这个结果有两个信息。

一个是节点值。

另一个是层级边界。

只把节点按访问顺序吐出来还不够。3, 9, 20, 15, 7 只是访问顺序，它没有告诉我们哪几个节点属于同一层。

所以这题的重点不是「怎么走完整棵树」。

而是「怎么在走的过程中，知道当前这一层到哪里结束」。

很多人第一次写这题，会卡在这里。

看起来队列能把节点按顺序拿出来，但队列里一边弹出当前层，一边又把下一层塞进去。两层节点混在同一个队列里，边界好像一下就糊了。

这时就轮到 levelSize 出场。

二、为什么队列刚好适合这件事

队列是一种先进先出的结构。

你可以把它理解成排队买咖啡。先来的人先被服务，后来的人排到后面。

二叉树的层序遍历刚好也是这个秩序。

根节点先进去。

取出根节点时，把它的左孩子、右孩子放到队尾。

再取出第二层的节点时，把它们的孩子继续放到队尾。

这样一来，越靠近根节点的节点越早被处理，同一层的节点也会按从左到右的顺序出现。

这不是巧合。

这是队列和层序遍历的性格刚好对上了。

上面这张图里，最关键的不是入队，也不是出队。

是记录当前队列长度。

因为在这一刻，队列里装着的，正好都是当前这一层的节点。

下一层的节点还没被塞进去。

所以只要先记住这个长度，我们就能放心地循环 levelSize 次，把这一层完整切出来。

三、把一层从队列里切出来

我喜欢把 levelSize 理解成一把很小的刀。

它不负责遍历整棵树。

它只负责在每一轮开始时，对队列说一句，这一段属于当前层，后面新来的都先别混进来。

举个例子。

根节点 3 处理完之后，队列里是 9 和 20。

这一轮开始时，levelSize 等于 2。所以我们只处理两个节点。

处理 9 时，它没有孩子，队列变化不大。

处理 20 时，它的孩子 15 和 7 会进入队尾。

但这一轮不会继续处理 15 和 7。

因为 levelSize 已经提前说好了，这一层只处理两个。

这一点特别重要。

没有 levelSize，你很容易把下一层也顺手处理掉，最后结果就会变成一长串，而不是一层一层的数组。

这张 PlantUML 图表达的是同一件事。

当前层和下一层不靠节点值区分，也不靠深度字段区分。

它们靠一轮开始时的队列长度区分。

四、代码实现

力扣题里已经提供了 TreeNode 结构，所以我们只需要写 levelOrder 函数。

int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
    if (root == NULL) {
        *returnSize = 0;
        *returnColumnSizes = NULL;
        return NULL;
    }
 
    int capacity = 2000;
    int** result = malloc(sizeof(int*) * capacity);
    *returnColumnSizes = malloc(sizeof(int) * capacity);
    *returnSize = 0;
 
    struct TreeNode** queue = malloc(sizeof(struct TreeNode*) * capacity);
    int head = 0;
    int tail = 0;
    queue[tail++] = root;
 
    while (head < tail) {
        int levelSize = tail - head;
        int* level = malloc(sizeof(int) * levelSize);
 
        for (int i = 0; i < levelSize; i++) {
            struct TreeNode* node = queue[head++];
            level[i] = node->val;
 
            if (node->left != NULL) {
                queue[tail++] = node->left;
            }
 
            if (node->right != NULL) {
                queue[tail++] = node->right;
            }
        }
 
        result[*returnSize] = level;
        (*returnColumnSizes)[*returnSize] = levelSize;
        (*returnSize)++;
    }
 
    free(queue);
    return result;
}

这段代码里，我觉得最值得盯住的只有三处。

root == NULL 处理空树。

levelSize = tail - head 固定当前层长度。

for 循环只跑 levelSize 次，让新加入队列的孩子节点留到下一轮。

其余部分都很直觉。

看见左孩子，就放进队列。

看见右孩子，也放进队列。

因为题目要从左到右，所以左孩子要先入队，右孩子后入队。

五、几个容易错的地方

空树要返回空数组。

这不是特殊癖好，而是题目返回值类型决定的。没有任何层，自然就是 []。

单节点树要返回 [[root.val]]。

如果你的代码能自然处理这个情况，说明主循环写得比较干净。

左右孩子的顺序不能反。

层序遍历默认是从左到右。如果先把右孩子入队，结果就会在同一层里反过来。

在 C 语言里，队列通常不用真的删除数组头部元素。

用 head 和 tail 两个下标就够了。head 指向下一个要取出的节点，tail 指向下一个可以放入的位置。

这比每次移动数组元素更干净。

先把层的边界想清楚，比一开始就追求更漂亮的队列实现更重要。

六、复杂度怎么理解

时间复杂度是 O(n)。

这里的 n 是树里的节点数量。每个节点会被放进队列一次，也会被取出来一次。

如果把每一层的节点数量记成 $w_i$，整棵树的节点总数就可以写成：

层序遍历做的事，就是把这些层从上到下各扫一遍。

空间复杂度也是 O(n)。

队列在最宽的一层时可能装下很多节点，结果数组也会保存所有节点值。

如果只看额外队列空间，可以说它和树的最大宽度有关。

但在这道题里，返回值本身就要保存所有节点，所以整体空间按 O(n) 看更直接。

七、这题留下的东西

我觉得 LeetCode 102 的价值，不在于背会一段 BFS 模板。

真正值得留下的是这个动作。

在一轮开始时，先固定当前层的长度。

这句话很短，但它会反复出现在后面的二叉树题里。

比如锯齿形层序遍历。

比如找每一层最大值。

比如把每一层的节点拿出来做额外计算。

很多题只是换了皮，骨架还是这一套。

队列负责让节点按层来到你面前。

levelSize 负责告诉你，这一层到哪里结束。

一个负责顺序。

一个负责边界。

二叉树的层序遍历，就被这两个东西拆开了。