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

从“为什么不能只递归左右子树”开始

先预测：根10的左子树以6为根，右子树以14为根。若按普通前序递归根、左、右，输出会先深入4、8，再回到14；结果10、6、4、8、14、12、16并不是题目要求的10、6、14、4、8、12、16。

“从上到下打印二叉树”要求深度小的节点先输出；同一层还要从左到右。它就是层序遍历。递归调用栈天然偏向深度优先，而能保存当前层尚未访问节点和下一层刚发现的节点。

作者使用std::deque作为队列：根从尾部push_back；每次从头部front并pop_front；再把左、右孩子依次push_back。deque是具体容器，队列是这里使用的行为抽象。

先进先出怎样扩展局部左右顺序

把简称FIFO。父节点总在孩子之前入队，所以父层先于子层出队；同一父节点先放左孩子再放右孩子，所以左孩子先出队。

更关键的是不同父节点之间：同层左侧父节点更早出队，它的孩子也更早加入队尾；右侧父节点的孩子随后才加入。由此下一层的所有节点按“父节点从左到右，每个父节点先左后右”排列，恰好得到整层从左到右。

队列中可能同时存在当前层尾部和下一层头部，但不影响不分行输出。题32（二）才需要知道层边界；本问只要每次取全局最早发现的节点，连续打印即可。

忠实还原作者deque实现

作者函数接收BinaryTreeNode指针，空根直接返回。非空时只把真实节点入队，不放nullptr占位；输出用printf写在一行，每个值后有空格。

#include <cstdio>
#include <deque>
 
struct BinaryTreeNode {
    int m_nValue;
    BinaryTreeNode* m_pLeft;
    BinaryTreeNode* m_pRight;
};
 
void PrintFromTopToBottom(BinaryTreeNode* pRoot) {
    if (pRoot == nullptr) {
        return;
    }
 
    std::deque<BinaryTreeNode*> dequeTreeNode;
    dequeTreeNode.push_back(pRoot);
 
    while (!dequeTreeNode.empty()) {
        BinaryTreeNode* pNode = dequeTreeNode.front();
        dequeTreeNode.pop_front();
 
        std::printf("%d ", pNode->m_nValue);
 
        if (pNode->m_pLeft != nullptr) {
            dequeTreeNode.push_back(pNode->m_pLeft);
        }
        if (pNode->m_pRight != nullptr) {
            dequeTreeNode.push_back(pNode->m_pRight);
        }
    }
}

先输出再入孩子和先入孩子再输出，在没有回调副作用时值序列相同；但忠实源码是先pop、printf，再按左、右入队。若print回调可能抛异常，前者会让当前节点已从队列移除而孩子尚未发现，恢复策略需要另行设计。

把左右入队顺序颠倒仍是层序，却会让每层从右到左。只用一个孩子的偏斜树无法发现这个错误，必须有同时具备左右孩子的测试。

返回序列与泛型访问版本

工程代码通常把遍历与输出分离，返回值序列或接收访问回调。下面用std::queue表达行为，让底层默认deque负责存储：

#include <queue>
#include <vector>
 
struct TreeNode {
    int value;
    TreeNode* left = nullptr;
    TreeNode* right = nullptr;
};
 
std::vector<int> levelOrder(const TreeNode* root) {
    if (root == nullptr) {
        return {};
    }
 
    std::vector<int> result;
    std::queue<const TreeNode*> pending;
    pending.push(root);
 
    while (!pending.empty()) {
        const TreeNode* node = pending.front();
        pending.pop();
        result.push_back(node->value);
 
        if (node->left != nullptr) pending.push(node->left);
        if (node->right != nullptr) pending.push(node->right);
    }
    return result;
}

const指针声明遍历不修改节点。返回vector占O(n)结果空间；若直接流式访问，除输出外只需队列。回调版可在返回false时提前停止，适合查找“第一个满足条件的最浅节点”；但提前停止得到的是层序前缀，调用方要知道遍历未完成。

TypeScript若用数组模拟队列，不应每次shift删除首元素，因为实现可能移动后续元素。使用head索引只前移，尾部push，整次遍历保持线性：

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

遍历结束后queue数组仍持有全部节点引用，直到函数返回。超大树或长生命周期生成器可使用真正的双端队列或环形缓冲区，及时释放已消费槽位，避免head前方的引用延长节点生命周期。

时间与最大宽度空间界

在合法二叉树中，每个节点恰好出队一次；每条父子边最多检查一次，时间O(n)。结果容器另占O(n)，作者打印版本不保存结果。

辅助队列峰值与W同阶，空间O(W)。偏斜树每层只有一个节点，W为1；完全二叉树最后一层约占全部节点一半，最坏W为O(n)。

严格说队列在处理某层中途会同时保存本层剩余节点与下一层已入队孩子。把这些已发现但未访问的节点称为。其数量可能超过单个层宽，但对二叉树仍受常数倍W约束，所以渐进空间O(W)。只写O(h)是把它与深度优先递归栈混淆。

设当前层原有a个节点，已经处理k个；队列中还剩a减k个本层节点，外加这k个节点产生的至多2k个孩子，总数至多a加k，也就是不超过2a。下一层宽度本身又不超过2a，因此处理过程中的峰值与相邻两层较大宽度同阶，不会因为“同时跨层”变成O(nh)。这个计数给出了O(W)比直觉更精确的依据。

容器实现也影响实际内存。std::deque弹出头部后可逐步释放内部块，但标准不承诺每次pop都立刻归还操作系统；std::queue只是适配接口。若节点数量巨大且遍历长期运行，可以使用分块队列、容量指标和取消信号。对返回vector的版本，队列释放后结果仍保存n个值，所以报告内存时应分别列出辅助空间O(W)与输出空间O(n)。

若只需要输出前k个节点，提前停止能把时间限制为O(k)，但队列可能已经保存它们的孩子；停止后局部容器析构会释放这些指针槽位，不会销毁树节点。若队列存放拥有所有权的智能指针，复制、移动与树所有权模型必须重新设计，普通层序算法不应意外转移节点所有权。

作者五组测试怎样覆盖树形

Test1是三层完整树：根10，第二层6与14，第三层4、8、12、16，输出10、6、14、4、8、12、16。它锁定跨父节点的同层左右顺序。

Test2是全左链5、4、3、2、1；Test3是全右链1、2、3、4、5。两者都每层一个节点，验证缺失孩子不会入队，也不会访问空指针。Test4单节点1，Test5空树无输出。作者总计五组。

原测试先调用公共PrintTree显示结构，再打印“The nodes from top to bottom...”并调用被测函数，没有自动比较预期数组。现代测试应把输出收集为vector后逐项断言：

#include <cassert>
#include <vector>
 
void testLevelOrder() {
    TreeNode n4{4}, n8{8}, n12{12}, n16{16};
    TreeNode n6{6, &n4, &n8};
    TreeNode n14{14, &n12, &n16};
    TreeNode n10{10, &n6, &n14};
 
    assert(levelOrder(&n10) ==
           (std::vector<int>{10, 6, 14, 4, 8, 12, 16}));
 
    TreeNode l1{1}, l2{2, &l1, nullptr};
    TreeNode l3{3, &l2, nullptr};
    TreeNode l4{4, &l3, nullptr};
    TreeNode l5{5, &l4, nullptr};
    assert(levelOrder(&l5) ==
           (std::vector<int>{5, 4, 3, 2, 1}));
 
    TreeNode only{1};
    assert(levelOrder(&only) == std::vector<int>{1});
    assert(levelOrder(nullptr).empty());
}

还应单独构造左右值不同的两孩子节点，以防实现把入队顺序反了；Test1已经具备这一能力。若值可重复，只比较值序列无法确认访问了哪个节点，可收集节点地址或唯一ID。

树契约、共享节点与环

算法假设输入是有限无环二叉树，每个非根节点只有一个父节点。若两个父节点共享同一个孩子，函数会把该地址入队两次并输出两次；若孩子指回祖先，会无限循环。对一般图执行广度优先搜索必须增加visited集合，时间和空间都包含去重成本。

不应无条件给树版添加visited：它会额外占O(n)空间，并可能掩盖“输入本应是树却发生共享/成环”的数据错误。接口可在调试模式校验树形，在可信树结构上维持最简队列。

并发修改同样破坏遍历契约。另一个线程若删除队列中的节点会产生悬空指针；若新增孩子，输出可能混合两个时刻的结构。使用不可变节点、读锁或拥有生命周期的快照。只把指针声明为const不等于对象在其他线程中不可变。

输出式函数还要处理I/O失败。printf示例忽略错误；文件、网络或UI回调失败时，应停止遍历并传播错误，不能继续消耗队列后只报告最后一次状态。返回vector版把计算和I/O分开，更容易获得全有或全无的结果。

正确性证明

循环不变量是：队列从头到尾按深度非递减排列；同一深度内按树的从左到右顺序排列；已出队节点已经按目标顺序输出，未入队节点只能是队列中某节点的后代。

根入队时不变量成立。每次取队头得到当前最浅、同层最左的未访问节点；它的左、右孩子深度都加1，并在所有已发现同层或更浅节点之后加入队尾。父节点按左到右出队，孩子也按左后右加入，因此新队列仍满足不变量。

有限树中每次循环永久移除一个节点，每个孩子只由唯一父节点加入一次，最终队列为空。由不变量，输出恰好包含每个节点一次，并按从上到下、同层从左到右排列。

本章练习

概念说明

本章核心概念包括：先入先出。理解这些概念是掌握解题方法的关键，需要结合具体示例与边界条件反复练习。

本章回顾

1. 不分行从上到下打印二叉树就是层序遍历。
2. 队列先入先出，保证父层先于子层、同层从左到右。
3. 作者用deque尾部入队、头部出队，并按左、右孩子顺序加入。
4. 空树直接返回，nullptr不作为占位元素进入队列。
5. 每个节点入队出队一次，时间O(n)，辅助空间O(W)。
6. 返回序列便于测试，流式输出节省结果空间但要处理失败传播。
7. 五组官方树覆盖完整结构、左右偏斜、单节点与空树。
8. 一般图或成环结构需要visited，普通树契约下不应重复访问。

名词解释