面试题32（二）：分行从上到下打印二叉树

在层序队列上分别维护当前层待打印数与下一层已发现数，于计数归零时换行并完成下一层状态转移。

学习目标

  • 能用层序队列 + 双计数器（toBePrinted/nextLevel）分行打印二叉树
  • 能解释"动态队长 ≠ 当前层数量"的原因
  • 能完成层结束时的换行与下一层状态转移

从“队列里混着两层，哪里该”开始

先预测：处理根8后，中是6、10；处理6并加入5、7后，队列变成10、5、7。此时队长是3，但当前层只剩10一个节点。若把动态队长当作当前层数量，5、7会被误打印到第二行。

“分行从上到下打印二叉树”仍使用，但必须额外识别层边界。作者没有在每层开始读取queue.size，而是维护两个独立：toBePrinted，以及nextLevel。层结束后换行是分行打印的关键：toBePrinted 归零即触发换行，并把 nextLevel 转移为新一层计数。

BFS 逐行打印：双计数器判断层边界861057911逐行输出第1行8第2行610第3行57911双计数器：toBePrinted（当前层剩余） / nextLevel（下一层已入队）打印一个节点：toBePrinted − 1；其非空孩子入队：nextLevel + 1。toBePrinted == 0 → 当前层打完：换行，toBePrinted = nextLevel，nextLevel = 0。例：根层 toBePrinted=1；打 8 后其孩子 6,10 入队 nextLevel=2，toBePrinted 归 0 → 换行。当前层计数归零的瞬间下一层已全部入队，二者可安全转移；O(n) 时间、O(w) 队列空间。
当前层计数归零的瞬间，下一层节点已经全部进入队列，二者可安全转移并换行。

根入队时toBePrinted为1、nextLevel为0。每打印一个节点，前者减1；每发现一个非空孩子并入队，后者加1。当前层最后一个节点处理完时，前者恰为0，而后者恰好统计完整下一层。

分步1 / 3

层序入队

根节点入队，toBePrinted=1 表示当前层待打印数。

BFS 逐行打印：双计数器判断层边界861057911逐行输出第1行8第2行610第3行57911双计数器：toBePrinted（当前层剩余） / nextLevel（下一层已入队）打印一个节点：toBePrinted − 1；其非空孩子入队：nextLevel + 1。toBePrinted == 0 → 当前层打完：换行，toBePrinted = nextLevel，nextLevel = 0。例：根层 toBePrinted=1；打 8 后其孩子 6,10 入队 nextLevel=2，toBePrinted 归 0 → 换行。当前层计数归零的瞬间下一层已全部入队，二者可安全转移；O(n) 时间、O(w) 队列空间。
当前层计数归零的瞬间，下一层节点已经全部进入队列，二者可安全转移并换行。

两个的状态转移

作者每轮先读取并打印队头，再依次把左、右孩子入队并增加nextLevel，随后pop当前节点并减少toBePrinted。只有在toBePrinted归零时才输出换行。

事件计数更新语义
出队并打印节点toBePrinted减1消费当前层一个位置
左孩子非空入队nextLevel加1登记下一层一个节点
右孩子非空入队nextLevel加1维持同层左到右
toBePrinted不为0不换行当前层尚有节点
toBePrinted等于0换行；赋值nextLevel；清零nextLevel层边界完成
两个计数器分别记账，换行只发生在当前层最后一个节点完成之后。

执行时，必须按语义完成三件事：打印换行；把toBePrinted赋为nextLevel；将nextLevel清零。下一轮开始后，两个计数器重新分别代表当前层与尚未完整发现的下一层。

如果先清零nextLevel再赋值，下一层计数会丢失；如果只赋值不清零，后续孩子会累计以前层的数量；如果在孩子入队前判断toBePrinted，当前层最后一个节点的孩子尚未记入下一层。

忠实还原作者双计数实现

作者使用std::queue保存BinaryTreeNode指针，输出式接口对空树直接返回。左孩子先于右孩子入队，因此每行保持从左到右。

#include <cstdio>
#include <queue>
 
struct BinaryTreeNode {
    int m_nValue;
    BinaryTreeNode* m_pLeft;
    BinaryTreeNode* m_pRight;
};
 
void Print(BinaryTreeNode* pRoot) {
    if (pRoot == nullptr) {
        return;
    }
 
    std::queue<BinaryTreeNode*> nodes;
    nodes.push(pRoot);
    int nextLevel = 0;
    int toBePrinted = 1;
 
    while (!nodes.empty()) {
        BinaryTreeNode* pNode = nodes.front();
        std::printf("%d ", pNode->m_nValue);
 
        if (pNode->m_pLeft != nullptr) {
            nodes.push(pNode->m_pLeft);
            ++nextLevel;
        }
        if (pNode->m_pRight != nullptr) {
            nodes.push(pNode->m_pRight);
            ++nextLevel;
        }
 
        nodes.pop();
        --toBePrinted;
        if (toBePrinted == 0) {
            std::printf("\n");
            toBePrinted = nextLevel;
            nextLevel = 0;
        }
    }
}

源码用int计数。实际树节点数若可能超过int上限，应使用std::size_t；每次孩子入队后计数同步增加，不会出现负数。调试构建可以断言toBePrinted加nextLevel等于队列大小：队列中正好由当前层残余和下一层已发现节点两部分组成。

这条等式能精确定位同步错误：孩子已入队却忘记增加nextLevel时，队列大小比两计数之和大；空孩子被错误计数时，两计数之和又比队列大；节点pop后忘记减少toBePrinted，两边也立即相差1。只在换行时检查最终输出会把错误延迟到下一层，逐轮断言能把失败固定在第一次错误更新。生产构建可移除昂贵诊断，但测试版应在每次循环尾验证计数均非负、两数之和等于队长，并在队列非空时要求toBePrinted为正。

把pop放在计数递减前后不改变值，只要每轮恰处理一个节点；但孩子计数必须发生在层转移之前。作者先打印再pop，函数若I/O失败无法回滚已写内容，工程接口应让输出回调返回状态并立即停止。

是等价变体，不是作者源码

现代返回二维数组时，常用：缓存levelSize等于queue.size，然后固定循环levelSize次。因为这一时刻队列只含当前层；循环中新增孩子留给下一次外层循环。

#include <cstddef>
#include <queue>
#include <vector>
 
struct TreeNode {
    int value;
    TreeNode* left = nullptr;
    TreeNode* right = nullptr;
};
 
std::vector<std::vector<int>> levels(const TreeNode* root) {
    if (root == nullptr) return {};
 
    std::vector<std::vector<int>> result;
    std::queue<const TreeNode*> pending;
    pending.push(root);
 
    while (!pending.empty()) {
        const std::size_t levelSize = pending.size();
        std::vector<int> line;
        line.reserve(levelSize);
 
        for (std::size_t i = 0; i < levelSize; ++i) {
            const TreeNode* node = pending.front();
            pending.pop();
            line.push_back(node->value);
            if (node->left != nullptr) pending.push(node->left);
            if (node->right != nullptr) pending.push(node->right);
        }
        result.push_back(std::move(line));
    }
    return result;
}

快照版的levelSize等价于作者每层开始时的toBePrinted；循环期间pending中新增长度等价于nextLevel。前者以固定次数隐式统计下一层，后者在每个孩子入队时显式记账。

方案层边界来源适合输出特点
作者双计数逐节点递减当前层、累加下一层流式printf精确体现状态转移
层首快照每层开始缓存queue.size()二维结果更自然固定循环次数
哨兵nullptr层尾加入空标记不推荐默认使用多一次特殊分支
两个队列current与next交换边界直观容器状态更多
四种方法时间和渐进队列空间相同；作者源码应优先按双计数器理解。

哨兵法在每层末尾放nullptr，取到哨兵时换行并追加新哨兵。若忘记在队列只剩哨兵时停止，可能无限追加；同时真实节点类型与控制标记混在一起。两个队列current/next也正确，但单队列加计数更紧凑。

TypeScript队列与二维结果

数组加head索引避免shift搬移元素。当前层大小应在内层循环前冻结为queue.length减head，而不是把后者直接写进不断重新求值的循环条件：

type Node = {
  value: number;
  left: Node | null;
  right: Node | null;
};
 
function levels(root: Node | null): number[][] {
  if (root === null) return [];
 
  const queue: Node[] = [root];
  const result: number[][] = [];
  let head = 0;
 
  while (head < queue.length) {
    const levelSize = queue.length - head;
    const line: number[] = [];
 
    for (let i = 0; i < levelSize; ++i) {
      const node = queue[head++];
      line.push(node.value);
      if (node.left !== null) queue.push(node.left);
      if (node.right !== null) queue.push(node.right);
    }
    result.push(line);
  }
  return result;
}

若写成i小于queue.length减head，右侧表达式会随着head递增和孩子push同时变化，边界难以推断。固定levelSize既是正确性条件，也让每一行预分配、进度统计和取消检查更清楚。

作者六组测试的树形覆盖

Test1是三层完整树：8；第二行6、10；第三行5、7、9、11。它验证每行多个节点、不同父节点孩子的左右顺序和4个下一层节点计数。

Test2为全左链5、4、3、2；Test3为全右链5、4、3、2，每层各打印一个值。Test4单节点5，Test5空树无输出。Test6是不规则链：100的左孩子50，50的右孩子150，三行分别是100、50、150；它验证孩子方向变化不会影响层计数。

作者测试通过printf写预期和实际结果供人工比对，没有自动断言。Test6还遗漏DestroyTree调用，示例进程退出时由系统回收，但长期测试应释放树。章节复刻应保留算法行为，不应复制测试资源泄漏。

#include <cassert>
#include <vector>
 
void testLevels() {
    TreeNode n5{5}, n7{7}, n9{9}, n11{11};
    TreeNode n6{6, &n5, &n7};
    TreeNode n10{10, &n9, &n11};
    TreeNode n8{8, &n6, &n10};
    assert(levels(&n8) ==
           (std::vector<std::vector<int>>{
               {8}, {6, 10}, {5, 7, 9, 11}}));
 
    TreeNode n150{150};
    TreeNode n50{50, nullptr, &n150};
    TreeNode n100{100, &n50, nullptr};
    assert(levels(&n100) ==
           (std::vector<std::vector<int>>{
               {100}, {50}, {150}}));
 
    TreeNode only{5};
    assert(levels(&only) ==
           (std::vector<std::vector<int>>{{5}}));
    assert(levels(nullptr).empty());
}

全左链和全右链也应保留，防止只处理某一侧孩子。若值重复，应核对每行节点ID或地址，因为仅凭值无法发现同一节点被重复入队。

时间、空间与流式语义

每个节点入队、出队、打印一次，时间O(n)。辅助队列由层前沿控制，空间O(W)，W为最大层宽。二维结果额外保存n个值和h个行容器，输出空间O(n+h)，通常记作O(n)。

双计数只增加O(1)控制空间，不改变队列峰值。偏斜树队列峰值1但行数h等于n；完全树行数约为log n但最后一层很宽。行数与宽度是两个独立维度，不能用树高替代队列空间。

流式打印的优势是无需保留全部结果，并且层结束即可刷新一行。若下游有背压，回调需要允许暂停或异步等待；队列中的节点必须在暂停期间保持有效。返回二维数组则在遍历成功后一次性交付，易测试但占更多内存。

输出空树时作者什么也不写，连空行也不由Print产生；测试包装函数额外printf换行。API应区分“树内容输出”和“测试格式”，否则空树可能多一行或少一行。

树契约与正确性证明

算法假设有限无环二叉树且每个非根节点只有一个父节点。共享孩子会被重复计入nextLevel并打印两次，环会使队列永不为空。一般图需要visited集合；普通树版本不应静默去重坏结构。

是：队列前toBePrinted个节点是当前层尚未打印部分，随后nextLevel个节点是下一层已发现部分；两数之和等于队列大小。当前层节点按左到右排列，下一层也按其父节点出队顺序及左后右排列。

处理一个当前层节点后，队头删除使toBePrinted减1；每个非空孩子加入队尾并使nextLevel同增，不变量保持。toBePrinted归零时，队列只含完整下一层，赋值转移后它们全部成为新当前层，换行位置恰在两层之间。

有限树每个节点由唯一父节点入队一次，最终队列为空。由不变量，每个节点恰输出一次，每行包含且仅包含同一深度节点，并保持从左到右。

本章练习

练习

问题 1： 为什么不能用 queue.size() 当当前层数量？

问题 2： 两个计数器各自维护什么？

问题 3： 层结束时如何状态转移？

概念说明

本章核心概念包括：当前层剩余节点数，下一层节点数。理解这些概念是掌握解题方法的关键，需要结合具体示例与边界条件反复练习。

本章回顾

  1. 分行层序遍历需要在普通队列之外识别当前层终点。
  2. toBePrinted记录当前层剩余节点数，nextLevel记录下一层节点数。
  3. 出队后当前层减一，非空孩子入队后下一层加一。
  4. 当前层归零时换行、转移下一层计数并清零旧账本。
  5. 层首快照levelSize是等价变体，但不是作者源码实现。
  6. 动态queue.size混合两层，不能直接作为不断变化的循环边界。
  7. 时间O(n)、辅助空间O(W)，二维输出另占O(n)。
  8. 作者六组测试覆盖完整、偏斜、单点、空树与不规则三层树。

名词解释

名词解释

本章出现的专业名词，用大白话再讲一遍。

层计数器
记录当前层剩余与下一层节点的两个独立变量。
状态转移
当前层处理完时，下一层计数转移为当前层的操作。
层首快照
记录每层开始时队列长度的等价实现变体。
层序遍历
按层从左到右的 BFS 遍历方式。
队列
先进先出结构，层序遍历的载体。
换行
当前层计数归零时输出换行的操作。
复习本章（4 题）

讨论

评论区加载中…