面试题32（三）：之字形打印二叉树

从“为什么普通队列还要整行反转”开始

先预测：根8的第二层是4、12，题目要求第二行输出12、4；第三层又恢复2、6、10、14。普通层序队列总按4、12输出，只能事后反转结果。能否选择一种容器，让正确方向直接从容器顶端产生？

作者用“两个栈”。一个负责本层弹出，另一个接收孩子。栈的后进先出会反转压入顺序，因此当前层必须根据下一层期望方向决定先压哪个孩子。

这正是“之字形打印二叉树”：第一行从左到右，第二行从右到左，第三行再从左到右，之后交替。根是第1层，也就是奇数层。

奇偶层的孩子压栈顺序

作者用levels[0]和levels[1]两个栈，current初值0、next初值1。栈0处理奇数层，栈1处理偶数层。

当current为0时，本层按左到右弹出。为让下一层按右到左弹出，对每个节点按左孩子、右孩子的次序压入栈1；右孩子后入先出。也就是原书概念“奇数层先左后右”压孩子。

当current为1时，本层按右到左弹出。为让再下一层按左到右弹出，对每个节点按右孩子、左孩子压入栈0；左孩子后入先出。这对应“偶数层先右后左”压孩子。

这里的“先左后右”描述压栈动作，不是说偶数层也按左到右输出。压入与弹出方向恰好相反；若只背输出箭头而不推压栈顺序，很容易把第二层做对、第三层做反。

忠实还原作者双栈实现

本层处理时只从levels[current]弹，只向levels[next]压。当前栈清空才输出换行，并让两个索引分别变成1减自身，交换角色。

#include <cstdio>
#include <stack>
 
struct BinaryTreeNode {
    int m_nValue;
    BinaryTreeNode* m_pLeft;
    BinaryTreeNode* m_pRight;
};
 
void Print(BinaryTreeNode* pRoot) {
    if (pRoot == nullptr) {
        return;
    }
 
    std::stack<BinaryTreeNode*> levels[2];
    int current = 0;
    int next = 1;
    levels[current].push(pRoot);
 
    while (!levels[0].empty() || !levels[1].empty()) {
        BinaryTreeNode* pNode = levels[current].top();
        levels[current].pop();
        std::printf("%d ", pNode->m_nValue);
 
        if (current == 0) {
            if (pNode->m_pLeft != nullptr) {
                levels[next].push(pNode->m_pLeft);
            }
            if (pNode->m_pRight != nullptr) {
                levels[next].push(pNode->m_pRight);
            }
        } else {
            if (pNode->m_pRight != nullptr) {
                levels[next].push(pNode->m_pRight);
            }
            if (pNode->m_pLeft != nullptr) {
                levels[next].push(pNode->m_pLeft);
            }
        }
 
        if (levels[current].empty()) {
            std::printf("\n");
            current = 1 - current;
            next = 1 - next;
        }
    }
}

外层条件检查两栈至少一个非空。根据角色不变量，循环开始时current栈必非空：本层结束切换后，若next层没有节点，则两栈都空，外层退出；若有节点，新current就是原next。因此top不会落在空栈。

可只写current等于1减current，再令next等于1减current吗？不可以，第二句会基于已更新的current，导致两个索引相同。作者分别对旧current与旧next取反，始终保持二者一个0、一个1。也可使用std::swap(current,next)，意图更直接。

调试双栈实现时，可以在每轮入口断言current与next不同且两者之和为1；处理一个节点期间，current栈大小只减少，next栈大小只增加；触发换行时旧current必须为空。交换后若两栈并非全空，新current必须非空，否则下一轮top会违反前提。再记录每层开始时的方向和节点总数，处理结束时输出数必须与该总数一致。这些局部检查能区分“孩子压错栈”“索引切换错误”和“左右顺序错误”，比只比较最后一串值更容易定位。

若改用两个具名变量currentLevel与nextLevel，交换容器本身也可避免整数索引算术；但std::stack交换后，调试日志里的对象身份会改变。数组加索引与具名栈都正确，关键契约是本层消费和下一层生产永不落到同一个容器。

为什么双栈能保持跨父节点顺序

考虑奇数层从左到右弹出父节点A、B。A先把左、右孩子压入下一栈，B随后把左、右孩子压在更上方。下一层弹出时先得到B的右、左孩子，再得到A的右、左孩子，正是整层从最右到最左。

偶数层则从右到左处理父节点B、A；每个父节点先压右、再压左。A后处理，其左、右相关节点位于栈顶区域，下一层先弹A左、A右，再到B左、B右，恢复从左到右。

把分成两级看：父节点处理顺序被整个栈反转；每个父节点内部的孩子压入顺序也被反转。二者共同得到下一层完整方向，不是每个兄弟对局部交换就够。

队列加下标填充的现代等价版

也可以始终用队列按左到右层序取节点，为每层预分配结果数组。左到右层把第i个节点写到i，右到左层写到levelSize减1再减i；这样不需要最后reverse，也不改变孩子入队顺序。

#include <cstddef>
#include <queue>
#include <vector>
 
struct TreeNode {
    int value;
    TreeNode* left = nullptr;
    TreeNode* right = nullptr;
};
 
std::vector<std::vector<int>> zigzag(const TreeNode* root) {
    if (root == nullptr) return {};
 
    std::vector<std::vector<int>> result;
    std::queue<const TreeNode*> pending;
    pending.push(root);
    bool leftToRight = true;
 
    while (!pending.empty()) {
        const std::size_t count = pending.size();
        std::vector<int> line(count);
 
        for (std::size_t i = 0; i < count; ++i) {
            const TreeNode* node = pending.front();
            pending.pop();
            const std::size_t target =
                leftToRight ? i : count - 1 - i;
            line[target] = node->value;
 
            if (node->left != nullptr) pending.push(node->left);
            if (node->right != nullptr) pending.push(node->right);
        }
        result.push_back(std::move(line));
        leftToRight = !leftToRight;
    }
    return result;
}

队列版把“结构发现顺序”和“展示方向”分离，适合返回二维数组；作者双栈版直接按目标顺序流式printf，无需保留整行再重排。两者时间O(n)、辅助前沿空间O(W)，选择取决于是否需要流式方向输出。

若使用queue加整行reverse，反转总成本跨所有层仍是O(n)，不是O(n²)。但按目标下标写入少一次反转遍历；双端队列从两端插入也可实现，却更容易把孩子访问与结果排列混淆。

作者七组测试如何验证方向

Test1三层树输出8；10、6；5、7、9、11，能验证一次右向和一次恢复左向。Test2全左链、Test3全右链，每层只有一个节点，覆盖缺失孩子但看不出方向；Test4单节点，Test5空树。

Test6是不规则链100的左孩子50、50的右孩子150，每层仍一个节点，验证左右孩子分支都能进入下一栈。与题32（二）相同，作者此测试未调用DestroyTree，长期测试应补释放。

Test7是4层满树，输出8；12、4；2、6、10、14；15、13、11、9、7、5、3、1。第四色行有8个值，能检验多个父节点的全层反向，而不只是相邻兄弟交换。源码总计七组。

#include <cassert>
#include <vector>
 
void testZigzag() {
    TreeNode n1{1}, n3{3}, n5{5}, n7{7};
    TreeNode n9{9}, n11{11}, n13{13}, n15{15};
    TreeNode n2{2, &n1, &n3};
    TreeNode n6{6, &n5, &n7};
    TreeNode n10{10, &n9, &n11};
    TreeNode n14{14, &n13, &n15};
    TreeNode n4{4, &n2, &n6};
    TreeNode n12{12, &n10, &n14};
    TreeNode n8{8, &n4, &n12};
 
    assert(zigzag(&n8) ==
           (std::vector<std::vector<int>>{
               {8},
               {12, 4},
               {2, 6, 10, 14},
               {15, 13, 11, 9, 7, 5, 3, 1}}));
 
    TreeNode only{5};
    assert(zigzag(&only) ==
           (std::vector<std::vector<int>>{{5}}));
    assert(zigzag(nullptr).empty());
}

完整自动测试还应保留左右链与100、50、150稀疏树。对双栈实现，可把printf替换为行收集器，同时断言每次换行时旧current为空、新current等于旧next，两个索引互补。

方向编号、稀疏树与空孩子

本章把根称为第1层，所以奇数层左到右、偶数层右到左。若代码用零基depth，depth为偶数对应左到右；变量名用leftToRight比判断level模2更不易出现编号偏差。

作者不把nullptr压栈。稀疏树只按真实节点形成每行顺序；若为了序列化形状而加入空占位，空节点也会产生孩子占位，必须设置深度或终止规则，否则数量指数增长。打印值的问题不需要占位。

方向只在翻转，不能每处理一个节点就翻。单节点层会让错误实现暂时看似正确，因此方向测试必须包含至少两层宽度大于1的树。

如果输出回调在一层中途失败，已输出前缀无法撤回，两个栈仍保存未处理状态。接口可返回当前层号、方向和剩余栈，允许幂等续传；简单函数应立即停止并传播错误。

时间、空间与树契约

每个节点进入某个栈一次、弹出一次，时间O(n)。两个栈并非各自都长期保存O(W)后再相加成更高阶；本层残余与下一层已发现共同构成层前沿，总辅助空间O(W)。返回二维数组另占O(n)。

算法假设有限无环树且每个节点唯一父亲。共享孩子会在两个路径下重复压栈，环会无限打印。一般图需要visited，但“之字形层”对图还需定义同层多父发现顺序；原题不承担这类语义。

并发修改会破坏指针生命周期和层方向。使用不可变树、读锁或快照。若节点值读取本身可能抛异常，流式输出可能留下部分行；返回容器版可以先完成计算再交付。

正确性证明

是：current栈从顶到底按本层目标输出顺序排列；next栈保存已发现的下一层节点，其顶端方向正逐步构造成下一层目标顺序；两个栈不混层。

奇数层从左到右弹父节点，并按左、右压孩子。由于LIFO，后处理的右侧父节点孩子先弹，每个父节点又是右孩子先弹，所以下一层整体从右到左。偶数层对称地从右到左弹父节点、按右左压孩子，下一层整体恢复左到右。

current清空说明本层全部且仅这些节点已输出；交换后next成为新current，已有次序由上段论证正确。根层初始只有根，归纳到所有有限层，得到每个节点恰输出一次且方向逐层交替。

本章练习

本章回顾

1. 之字形打印让奇数层左到右、偶数层右到左。
2. 作者使用两个栈，current只弹本层，next只接收孩子。
3. 奇数层先左后右压孩子，使偶数层右到左弹出。
4. 偶数层先右后左压孩子，使奇数层恢复左到右。
5. 当前栈清空才换行并交换两个索引，层间不能混栈。
6. 队列加目标下标是等价返回版，作者源码则可直接流式输出。
7. 时间O(n)、辅助空间O(W)，结果空间O(n)。
8. 七组官方测试中四层满树锁定整层反向而非局部兄弟交换。

名词解释