企业官网建设流程全解析

• 示例工程
• 教程

导读：本文围绕《剑指 Offer（第 2 版）》第 32 题的第三个变体「从上到下打印二叉树 III」展开，讲解如何在普通层序遍历的基础上实现「之字形 / 锯齿形」打印——奇数层从左到右、偶数层从右到左交替输出。你将掌握 BFS + 按层反转的核心套路，并拿到 Python、Java、C++、Go、TypeScript、Rust、JavaScript、C# 八种语言的完整可运行实现，同时通过仓库源码（Solution.java、Solution.py 等）理解其与 32-I、32-II 两个前置变体的递进关系。

题目背景：一道题的三个递进变体

「从上到下打印二叉树」是《剑指 Offer》中考察二叉树遍历的经典系列，仓库中 lcof 目录下依次收录了三个变体：

三者共享同一棵示例二叉树：

3 / \ 9 20 / \ 15 7

其中 III 变体要求：第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推，最终返回：

[ [3], [20,9], [15,7] ]

题目同时给出约束：节点总数<= 1000，意味着 $O(n)$ 的遍历方案在时空上都是完全安全的。

思路分析：为什么是「BFS + 按层反转」

从 32-I 到 32-III 的演进逻辑

• 32-I只需要"从上到下、从左到右"的扁平输出，一个普通队列即可完成，属于最朴素的 BFS。
• 32-II要求"每层单独成行"，关键在于出队前先记录当前队列长度n，一次循环恰好处理一整层，从而保留层的边界。
• 32-III在 32-II 的基础上增加了"奇偶层方向相反"的约束。最直接的做法是：每一层仍然统一按照从左到右的顺序从队列中收集节点，收集完一整层之后，再根据当前层号（即已经收集到的层数）的奇偶性决定是否反转。

原文档的思考块对该策略有一个非常精辟的总结：

锯齿层序仍按层访问，只是奇数层方向相反。用双端队列两端弹出可行，但实现更绕。先按从左到右收集一层，若当前答案层数为奇数则反转该层再写入，孩子仍按左右入队。

也就是说，入队阶段完全不用关心方向——左右孩子始终按"先左后右"入队；反转动作推迟到整层收集完成之后统一进行。这样做的好处是思路清晰、各语言实现完全同构，避免了双端队列那种"不同层从不同端弹出、孩子入队方向还要跟着翻转"的繁琐写法。

核心判定：当前层是奇数层还是偶数层

由于根节点所在的第一层按从左到右输出，而ans在收集第一层之前长度为0（偶数），因此判定规则为：

• 当ans中已收集的层数为偶数（即len(ans) % 2 == 0，对应第 1、3、5… 层）时，直接按原序写入；
• 当ans中已收集的层数为奇数（即len(ans) % 2 == 1，对应第 2、4、6… 层）时，先反转本层再写入。

注意一个细节：仓库中不同语言的判定写法略有差异——Python、Java、C++、Go、JavaScript、C# 直接依据len(ans)/ans.size()的奇偶性判断；而 TypeScript、Rust 则用独立的isEven/is_even布尔标志位逐层取反。两种方式语义完全等价，前者更省状态，后者可读性更直观。

核心算法流程

1. 判空：若root为空，直接返回空数组（各语言返回类型见下文代码）。
2. 初始化：将根节点入队；准备结果数组ans。
3. 按层遍历：只要队列非空，就记录当前队列长度n，然后连续出队n个节点：
   • 将节点值加入本层临时数组t；
   • 依次将node.left、node.right（非空时）入队。
4. 方向处理：t收集完毕后，若当前已收集层数为奇数，则反转t。
5. 写入结果：将t加入ans，继续下一层。
6. 队列为空时遍历结束，返回ans。

以示例二叉树为例，手工推演一遍：

• 第 1 层：队列[3]，收集[3]，ans长度 0（偶数），不反转 →[3]；
• 第 2 层：队列[9,20]，收集[9,20]，ans长度 1（奇数），反转 →[20,9]；
• 第 3 层：队列[15,7]，收集[15,7]，ans长度 2（偶数），不反转 →[15,7]。

最终得到[[3],[20,9],[15,7]]，与题目示例完全一致。

复杂度分析

• 时间复杂度 $O(n)$：每个节点恰好入队一次、出队一次；整层反转累计耗时 $O(n)$。其中 $n$ 为二叉树的节点数。
• 空间复杂度 $O(n)$：队列最多同时容纳一整层节点（最坏情况为满二叉树的最后一层，规模约 $n/2$），结果数组本身也需 $O(n)$ 空间。

多语言完整实现

以下实现均取自仓库 lcof/面试题32 - III. 从上到下打印二叉树 III 目录，与 README.md 中的解法一一对应。

Python3

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def levelOrder(self, root: TreeNode) -> List[List[int]]: ans = [] if root is None: return ans q = deque([root]) ans = [] while q: t = [] for _ in range(len(q)): node = q.popleft() t.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) ans.append(t[::-1] if len(ans) & 1 else t) return ans

Python 的写法最为简洁：t[::-1] if len(ans) & 1 else t一行完成"奇数层反转、偶数层原样"的分支判断，& 1等价于% 2 == 1。

Java

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> ans = new ArrayList<>(); if (root == null) { return ans; } Deque<TreeNode> q = new ArrayDeque<>(); q.offer(root); while (!q.isEmpty()) { List<Integer> t = new ArrayList<>(); for (int n = q.size(); n > 0; --n) { TreeNode node = q.poll(); t.add(node.val); if (node.left != null) { q.offer(node.left); } if (node.right != null) { q.offer(node.right); } } if (ans.size() % 2 == 1) { Collections.reverse(t); } ans.add(t); } return ans; } }

对应源码见 Solution.java。Java 使用ArrayDeque作为队列，for (int n = q.size(); n > 0; --n)的倒序循环写法保证一次循环恰好处理一整层。

C++

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> ans; if (!root) { return ans; } queue<TreeNode*> q{{root}}; while (!q.empty()) { vector<int> t; for (int n = q.size(); n; --n) { auto node = q.front(); q.pop(); t.push_back(node->val); if (node->left) { q.push(node->left); } if (node->right) { q.push(node->right); } } if (ans.size() & 1) { reverse(t.begin(), t.end()); } ans.emplace_back(t); } return ans; } };

对应源码见 Solution.cpp。C++ 使用std::reverse完成就地反转，ans.size() & 1判断奇数层，emplace_back(t)直接移动构造，避免一次拷贝。

Go

/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func levelOrder(root *TreeNode) (ans [][]int) { if root == nil { return } q := []*TreeNode{root} for len(q) > 0 { t := []int{} for n := len(q); n > 0; n-- { node := q[0] q = q[1:] t = append(t, node.Val) if node.Left != nil { q = append(q, node.Left) } if node.Right != nil { q = append(q, node.Right) } } if len(ans)&1 == 1 { for i, j := 0, len(t)-1; i < j; i, j = i+1, j-1 { t[i], t[j] = t[j], t[i] } } ans = append(ans, t) } return }

对应源码见 Solution.go。Go 用切片模拟队列（q = q[1:]弹出队首），反转时使用经典的双指针交换写法，配合命名返回值(ans [][]int)，空树直接return即可。

TypeScript

/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */ function levelOrder(root: TreeNode | null): number[][] { const res = []; if (root == null) { return res; } let isEven = false; const queue = [root]; while (queue.length !== 0) { const n = queue.length; const vals = new Array(n); for (let i = 0; i < n; i++) { const { val, left, right } = queue.shift(); vals[i] = val; left && queue.push(left); right && queue.push(right); } res.push(isEven ? vals.reverse() : vals); isEven = !isEven; } return res; }

对应源码见 Solution.ts。注意 TypeScript 版本采用独立的isEven标志位逐层取反：初始为false（第 1 层从左到右），每处理完一层翻转一次；vals预先分配new Array(n)长度，通过下标写入避免动态扩容。

Rust

// Definition for a binary tree node. // #[derive(Debug, PartialEq, Eq)] // pub struct TreeNode { // pub val: i32, // pub left: Option<Rc<RefCell<TreeNode>>>, // pub right: Option<Rc<RefCell<TreeNode>>>, // } // // impl TreeNode { // #[inline] // pub fn new(val: i32) -> Self { // TreeNode { // val, // left: None, // right: None // } // } // } use std::cell::RefCell; use std::collections::VecDeque; use std::rc::Rc; impl Solution { pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> { let mut res = Vec::new(); if root.is_none() { return res; } let mut queue = VecDeque::new(); queue.push_back(root); let mut is_even = false; while !queue.is_empty() { let n = queue.len(); let mut vals = Vec::with_capacity(n); for _ in 0..n { let mut node = queue.pop_front().unwrap(); let mut node = node.as_mut().unwrap().borrow_mut(); vals.push(node.val); if node.left.is_some() { queue.push_back(node.left.take()); } if node.right.is_some() { queue.push_back(node.right.take()); } } if is_even { vals.reverse(); } res.push(vals); is_even = !is_even; } res } }

对应源码见 Solution.rs。Rust 版本同样使用is_even标志位，并利用Vec::with_capacity(n)预分配容量；由于树节点是Rc<RefCell<TreeNode>>，出队后需要borrow_mut()获取可变借用，取走左右孩子时用node.left.take()直接移出所有权。

JavaScript

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {number[][]} */ var levelOrder = function (root) { const ans = []; if (!root) { return ans; } const q = [root]; while (q.length) { const t = []; for (let n = q.length; n; --n) { const { val, left, right } = q.shift(); t.push(val); left && q.push(left); right && q.push(right); } if (ans.length & 1) { t.reverse(); } ans.push(t); } return ans; };

对应源码见 Solution.js。JavaScript 借助数组解构const { val, left, right } = q.shift()一步取出节点值与左右孩子，ans.length & 1判断奇数层，Array.prototype.reverse就地反转。

C#

/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int x) { val = x; } * } */ public class Solution { public IList<IList<int>> LevelOrder(TreeNode root) { var ans = new List<IList<int>>(); if (root == null) { return ans; } var q = new Queue<TreeNode>(); q.Enqueue(root); while (q.Count > 0) { var t = new List<int>(); for (int n = q.Count; n > 0; --n) { var node = q.Dequeue(); t.Add(node.val); if (node.left != null) { q.Enqueue(node.left); } if (node.right != null) { q.Enqueue(node.right); } } if (ans.Count % 2 == 1) { t.Reverse(); } ans.Add(t); } return ans; } }

对应源码见 Solution.cs。C# 返回类型为IList<IList<int>>，使用Queue<TreeNode>作为队列，List<T>.Reverse()完成反转。

源码级佐证：解法的一致性验证

仓库中每个题解目录都会同时维护README.md与独立语言源文件，本题也不例外。将 README.md 中的代码块与目录下的Solution.*文件逐一比对，可以发现二者完全一致：

• Python：Solution.py
• Java：Solution.java
• C++：Solution.cpp
• Go：Solution.go
• TypeScript：Solution.ts
• Rust：Solution.rs
• JavaScript：Solution.js
• C#：Solution.cs

这意味着本文给出的所有代码都可以直接复制提交验证，文档与源码互为印证，不存在"文档写一套、代码跑另一套"的问题。

与主站 103 题的关系

从仓库结构可以观察到，该题与主站 LeetCode 103. 二叉树的锯齿形层序遍历 是同一思路的对应题目。主站版本的方法名为zigzagLevelOrder，其 Solution.java 采用boolean left标志位控制方向：left == true时直接写入，否则Collections.reverse(t)后再写入，随后left = !left取反。

对比之下可以发现两种标志位写法的细微差别：

• 剑指 Offer 版本以ans当前长度判断奇偶（第 2、4、6… 层反转）；
• 主站 103 题以left布尔标志记录下一个方向（初始为 true，代表第一层从左到右）。

两者本质相同，都是"整层收集 + 方向反转"，只是状态表达方式不同。理解这一点后，无论面试中遇到剑指 Offer 版本还是主站版本，都可以自由切换。

边界情况与易错点总结

1. 空树：root == null时必须返回空数组而非[[]]，所有语言实现的首个分支都在处理这一点。
2. 奇数层判定的基准：反转判断依据是"已经收集的层数"（len(ans)），而非"当前层的序号"。第一层收集前len(ans) == 0，不反转，符合题意。
3. 孩子入队顺序始终固定：统一"先左后右"入队，方向调整完全交给收集后的反转，不要在入队阶段尝试改变顺序，否则会破坏下一层的自然排列。
4. 单层循环的边界：必须先用n = q.size()固定本层节点数，否则循环中孩子不断入队会导致"一层被拆成多层"。
5. 关于双端队列方案：确实可以用双端队列从两端弹出实现（奇数层从队尾弹、偶数层从队头弹），但入队时孩子顺序同样需要按层反转，实现复杂度明显更高，且各语言对双端队列的支持程度不一（如 Python 的deque、C++ 的deque、Java 的ArrayDeque均可用，但代码量更大）。仓库统一选择了"先收集再反转"的简洁路线。

小结

「从上到下打印二叉树 III」是二叉树层序遍历的经典进阶题：它不改变 BFS 的骨架，只在"整层收集"之后追加一次方向反转。掌握这道题，意味着你已经同时吃透了 32-I（基础 BFS）、32-II（按层分组）与 32-III（锯齿形方向控制）三个递进层次，而仓库中 8 种语言同构的实现，也为多语言对比学习提供了极佳的范本。面试遇到同类题目时，先确认"是否需要保留层边界"，再确认"层内方向是否有奇偶变化"，就能快速锁定正确的 BFS 变体。

• 示例工程
• 教程