InterviewGuide 剑指 Offer 刷题笔记:面试题 32-III「从上到下打印二叉树 III」之字形层序遍历的双栈与队列反转双解法

原创2026-10-12 15:06:061,360 阅读
文章标签:文档知识库教程

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]
]

提示:

  1. 节点总数 <= 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. 第 1 层:left_right 中只有根节点 3,弹出后 temp = [3];随后先左后右把 9、20 压入 right_right。栈底到栈顶为 [9, 20]。
  2. 第 2 层:从 right_left 弹栈,后入栈的 20 先出,再出 9,得到 temp = [20, 9],恰好是从右到左!随后先右后左把 20 的孩子 7、15 压入 left_right(栈底到栈顶 [7, 15])。
  3. 第 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-III.从上到下打印二叉树III

登录后查看全文
InterviewGuide