InterviewGuide 剑指 Offer 刷题笔记:面试题 32-III「从上到下打印二叉树 III」之字形层序遍历的双栈与队列反转双解法
InterviewGuide 剑指 Offer 刷题笔记:面试题 32-III「从上到下打印二叉树 III」之字形层序遍历的双栈与队列反转双解法
本篇技术指南围绕 InterviewGuide 仓库中收录的剑指 Offer 经典原题「面试题 32 - III. 从上到下打印二叉树 III」展开,完整讲解"之字形"层序遍历的题意、示例与两条可运行的 C++ 解题路径:双栈来回导出法、单队列加奇偶层反转法。读完本文,你将掌握这类"按层交替方向遍历二叉树"问题的两种代码实现、各自的正确性原理与时空复杂度,并能在笔试面试中快速给出可落地的解法。
题目回顾:之字形打印二叉树
原题要求实现一个函数,按照之字形(Zigzag)顺序打印二叉树:第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。即奇数层(从 1 开始计数)从左到右,偶数层从右到左交替输出。
题目给出的示例二叉树为 [3,9,20,null,null,15,7],其结构如下:
3
/ \
9 20
/ \
15 7
返回的层次遍历结果为:
[
[3],
[20,9],
[15,7]
]
提示:
节点总数 <= 1000
注意第一层输出 [3],第二层输出 [20,9](从右到左),第三层输出 [15,7](从左到右),方向逐层交替——这正是与普通层序遍历最本质的区别。
题意拆解:从 32-I 到 32-III 的递进
这道题是剑指 Offer 面试题 32 系列的第三问,InterviewGuide 仓库中完整收录了该系列的三道题目,可以对照阅读,体会层序遍历的三种递进难度:
| 题目 | 输出要求 | 数据组织方式 | 仓库文档 |
|---|---|---|---|
| 32-I 从上到下打印二叉树 | 单层单层顺序拼接成一维数组 | 一个队列直接 BFS | 面试题32-I.从上到下打印二叉树 |
| 32-II 从上到下打印二叉树 II | 每层打印到一行,返回二维数组 | 队列 + 记录每层节点数 | 面试题32-II.从上到下打印二叉树II |
| 32-III 从上到下打印二叉树 III | 每层一行,且方向逐层交替 | 双栈交替,或队列 + 奇偶层反转 | 本文 |
32-III 是 32-II 的进阶版:在"按层分行"的基础上,增加了"相邻两层方向相反"的约束。因此,凡是能解决 32-II 的层序遍历框架(双队列交替、单队列按层计数),都可以在其基础上增加"奇偶层方向控制"来求解 32-III。
解法一:双栈来回导出(经典剑指 Offer 思路)
核心思想
栈具有 LIFO(后进先出) 特性:如果按"先左后右"的顺序把节点压入一个空栈,下一次弹栈时就会得到"从右到左"的逆序输出;反之,按"先右后左"压栈,弹栈就会得到"从左到右"的正序输出。
因此可以准备两个栈:
left_right:负责输出"从左到右"方向的层,同时把下一层节点先左后右压入right_left;right_left:负责输出"从右到左"方向的层,同时把下一层节点先右后左压入left_right。
两个栈来回交替使用,每弹出一层就换另一个栈处理下一层,天然实现方向交替。
完整代码(C++)
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
if (root == nullptr) return result;
stack<TreeNode*> left_right, right_left;
left_right.push(root);
TreeNode* node;
while (!left_right.empty() || !right_left.empty()) {
vector<int> temp;
// 奇数层:从左到右输出
while (!left_right.empty()) {
node = left_right.top();
left_right.pop();
temp.push_back(node->val);
if (node->left) // 注意这里是先左再右
right_left.push(node->left);
if (node->right)
right_left.push(node->right);
}
if (temp.size()) {
result.push_back(temp);
temp.clear();
}
// 偶数层:从右到左输出
while (!right_left.empty()) {
node = right_left.top();
right_left.pop();
temp.push_back(node->val);
if (node->right) // 这里是先右再左
left_right.push(node->right);
if (node->left)
left_right.push(node->left);
}
if (temp.size()) {
result.push_back(temp);
}
}
return result;
}
正确性推演:为什么"先左后右"和"先右后左"能反转方向
以题目示例 [3,9,20,null,null,15,7] 逐层模拟:
- 第 1 层:
left_right中只有根节点 3,弹出后temp = [3];随后先左后右把 9、20 压入right_right。栈底到栈顶为[9, 20]。 - 第 2 层:从
right_left弹栈,后入栈的 20 先出,再出 9,得到temp = [20, 9],恰好是从右到左!随后先右后左把 20 的孩子 7、15 压入left_right(栈底到栈顶[7, 15])。 - 第 3 层:从
left_right弹栈,后入栈的 15 先出,再出 7,得到temp = [15, 7],恢复从左到右。
规律一目了然:
- 当某一层需要反向(从右到左)输出时,就把它的孩子先左后右压入另一个栈,靠 LIFO 完成逆序;
- 当某一层需要正向(从左到右)输出时,就把它的孩子先右后左压入另一个栈,靠 LIFO 再逆序一次回到正序。
另外注意代码中两处 if (temp.size()) 的守卫:它保证在某一层恰好处理完毕、temp 为空时(例如最后一层没有孩子被压入)不会把空数组混入结果。以题目 1000 节点的规模上限,两个栈中任意时刻最多存放一层的节点,迭代实现不存在递归深度导致的栈溢出风险。
从复杂度看:每个节点恰好入栈一次、出栈一次,时间复杂度 O(n);两个栈合计最多同时存放一层的全部节点,空间复杂度 O(n)。
该解法为原文档中标注的剑指 Offer 官方思路,作者提交时的数据为:执行用时 0 ms、内存消耗 12.8 MB(LeetCode C++ 提交环境,仅供参考,实际性能随测试数据与编译器版本波动)。
解法二:单队列 + 奇偶层反转(一个栈/队列也可以做)
核心思想
只用一个普通队列做 BFS 层序遍历:先按 32-II 的方式,通过 rowLen = q.size() 固定当前层的节点数,把每层节点全部按从左到右的正向顺序收集进 temp;然后借助一个布尔标志位 isLeft 判断当前层是否应该反向输出,若需要反向,就用 vector 的逆序迭代器 rbegin()/rend() 一次性翻转。
完整代码(C++)
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
if (root == nullptr) {
return ans;
}
queue<TreeNode*> q;
q.push(root);
bool isLeft = false;
while (!q.empty()) {
int rowLen = q.size();
vector<int> temp;
for (int i = 0; i < rowLen; ++i) {
TreeNode* curNode = q.front();
q.pop();
if (curNode != nullptr) {
temp.push_back(curNode->val);
if (curNode->left) q.push(curNode->left);
if (curNode->right) q.push(curNode->right);
}
}
isLeft = !isLeft;
if (!isLeft) {
// 偶数层:翻转一次就做到了从右向左
ans.push_back(vector<int>(temp.rbegin(), temp.rend()));
} else {
ans.push_back(temp);
}
}
return ans;
}
关键细节:isLeft 标志与 rbegin()/rend() 反转
- 队列 BFS 本身只会产出"从左到右"的正向序列,所以方向控制完全交给输出环节;
isLeft初始为false,每处理完一层取反。第 1 层处理完后isLeft变为true,直接原样输出;第 2 层处理完后变为false,执行vector<int>(temp.rbegin(), temp.rend())构造一个完全逆序的新数组后再放入ans,实现从右到左;rbegin()/rend()返回反向迭代器,从容器末尾向开头遍历,用它构造新vector即可得到temp的逆序副本,原数组不会被破坏,逻辑直观、不易出错。
该解法的时空复杂度同样为 O(n):每个节点入队、出队一次;temp 与反转副本的临时空间、队列中最多存放的一层节点数均与树宽同阶。
作者提交时的数据为:执行用时 8 ms、内存消耗 12.9 MB(LeetCode C++ 提交环境,仅供参考)。相比解法一省去了"交替压栈时孩子入栈顺序需要区分先左后右/先右后左"的思维负担,编码更不易出错,属于"先统一正向收集、再按层反转"的通用套路,面试时更推荐优先写出这种写法。
两种解法对比与面试要点
| 维度 | 解法一:双栈来回导出 | 解法二:单队列 + 奇偶层反转 |
|---|---|---|
| 数据结构 | 两个 stack<TreeNode*> |
一个 queue<TreeNode*> + 布尔标志 |
| 方向控制位置 | 压栈阶段(孩子入栈顺序) | 输出阶段(rbegin/rend 反转) |
| 时间/空间复杂度 | O(n) / O(n) | O(n) / O(n) |
| 代码易错点 | 压栈顺序容易写反(先左后右 vs 先右后左) | 忘记按 rowLen 固定层宽,或 isLeft 取反时机错位 |
| 适用场景 | 剑指 Offer 原书思路,考察栈特性 | 在 32-II 框架上最小改动,通用性更强 |
面试中围绕此题常见的追问包括:
- 为什么栈能改变遍历方向? 利用 LIFO 的逆序特性,压栈顺序与弹栈顺序相反,只要控制孩子入栈的先后就能控制下一层的输出方向。
- 两个解法的时间复杂度为什么都是 O(n)? 每个节点在两个解法中都恰好被访问一次(入/出栈一次或入/出队一次),不存在重复访问。
- 能否用双端队列(deque)做? 可以,按层固定宽度后,偶数层从队头插入、奇数层从队尾插入即可,思路与解法二同源。
- 递归能做吗? 可以,但需要额外记录层号并按层号决定是否反转,递归深度在极端链表化二叉树下可达节点数规模,本题 1000 节点的上限下尚可,但迭代方案更稳。
延伸阅读
- 本系列上一问:面试题32-II.从上到下打印二叉树II(按层分行,含双队列与单队列两种写法)
- 本系列第一问:面试题32-I.从上到下打印二叉树(最朴素的队列层序遍历)
- 树专题完整题单:精选力扣300+题目之树
- 刷题专栏整体说明:精选力扣300+道算法题
本题所在文档:面试题32-III.从上到下打印二叉树III