剑指 Offer 32-III 从上到下打印二叉树 III:锯齿形(之字形)层序遍历的 BFS 解法全解析
剑指 Offer 32-III 从上到下打印二叉树 III:锯齿形(之字形)层序遍历的 BFS 解法全解析
导读:本文围绕《剑指 Offer(第 2 版)》第 32 题的第三个变体「从上到下打印二叉树 III」展开,讲解如何在普通层序遍历的基础上实现「之字形 / 锯齿形」打印——奇数层从左到右、偶数层从右到左交替输出。你将掌握 BFS + 按层反转的核心套路,并拿到 Python、Java、C++、Go、TypeScript、Rust、JavaScript、C# 八种语言的完整可运行实现,同时通过仓库源码(Solution.java、Solution.py 等)理解其与 32-I、32-II 两个前置变体的递进关系。
题目背景:一道题的三个递进变体
「从上到下打印二叉树」是《剑指 Offer》中考察二叉树遍历的经典系列,仓库中 lcof 目录下依次收录了三个变体:
| 题号 | 要求 | 输出形态 |
|---|---|---|
| 面试题 32 - I. 从上到下打印二叉树 | 从上到下、同层从左到右打印所有节点 | 一维数组 [3,9,20,15,7] |
| 面试题 32 - II. 从上到下打印二叉树 II | 按层打印,每层单独成行 | 二维数组 [[3],[9,20],[15,7]] |
| 面试题 32 - III. 从上到下打印二叉树 III(本文) | 之字形打印:奇层左→右、偶层右→左 | 二维数组 [[3],[20,9],[15,7]] |
三者共享同一棵示例二叉树:
3
/ \
9 20
/ \
15 7
其中 III 变体要求:第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推,最终返回:
[
[3],
[20,9],
[15,7]
]
题目同时给出约束:节点总数 <= 1000,意味着 的遍历方案在时空上都是完全安全的。
思路分析:为什么是「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布尔标志位逐层取反。两种方式语义完全等价,前者更省状态,后者可读性更直观。
核心算法流程
- 判空:若
root为空,直接返回空数组(各语言返回类型见下文代码)。 - 初始化:将根节点入队;准备结果数组
ans。 - 按层遍历:只要队列非空,就记录当前队列长度
n,然后连续出队n个节点:- 将节点值加入本层临时数组
t; - 依次将
node.left、node.right(非空时)入队。
- 将节点值加入本层临时数组
- 方向处理:
t收集完毕后,若当前已收集层数为奇数,则反转t。 - 写入结果:将
t加入ans,继续下一层。 - 队列为空时遍历结束,返回
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]],与题目示例完全一致。
复杂度分析
- 时间复杂度 :每个节点恰好入队一次、出队一次;整层反转累计耗时 。其中 为二叉树的节点数。
- 空间复杂度 :队列最多同时容纳一整层节点(最坏情况为满二叉树的最后一层,规模约 ),结果数组本身也需 空间。
多语言完整实现
以下实现均取自仓库 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 版本还是主站版本,都可以自由切换。
边界情况与易错点总结
- 空树:
root == null时必须返回空数组而非[[]],所有语言实现的首个分支都在处理这一点。 - 奇数层判定的基准:反转判断依据是"已经收集的层数"(
len(ans)),而非"当前层的序号"。第一层收集前len(ans) == 0,不反转,符合题意。 - 孩子入队顺序始终固定:统一"先左后右"入队,方向调整完全交给收集后的反转,不要在入队阶段尝试改变顺序,否则会破坏下一层的自然排列。
- 单层循环的边界:必须先用
n = q.size()固定本层节点数,否则循环中孩子不断入队会导致"一层被拆成多层"。 - 关于双端队列方案:确实可以用双端队列从两端弹出实现(奇数层从队尾弹、偶数层从队头弹),但入队时孩子顺序同样需要按层反转,实现复杂度明显更高,且各语言对双端队列的支持程度不一(如 Python 的
deque、C++ 的deque、Java 的ArrayDeque均可用,但代码量更大)。仓库统一选择了"先收集再反转"的简洁路线。
小结
「从上到下打印二叉树 III」是二叉树层序遍历的经典进阶题:它不改变 BFS 的骨架,只在"整层收集"之后追加一次方向反转。掌握这道题,意味着你已经同时吃透了 32-I(基础 BFS)、32-II(按层分组)与 32-III(锯齿形方向控制)三个递进层次,而仓库中 8 种语言同构的实现,也为多语言对比学习提供了极佳的范本。面试遇到同类题目时,先确认"是否需要保留层边界",再确认"层内方向是否有奇偶变化",就能快速锁定正确的 BFS 变体。