剑指 Offer 32-III 从上到下打印二叉树 III:锯齿形(之字形)层序遍历的 BFS 解法全解析

原创2026-10-14 13:27:571,999 阅读
文章标签:教程示例工程教育

剑指 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,意味着 O(n)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):每个节点恰好入队一次、出队一次;整层反转累计耗时 O(n)O(n)。其中 nn 为二叉树的节点数。
  • 空间复杂度 O(n)O(n):队列最多同时容纳一整层节点(最坏情况为满二叉树的最后一层,规模约 n/2n/2),结果数组本身也需 O(n)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.* 文件逐一比对,可以发现二者完全一致:

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

与主站 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 变体。

登录后查看全文
leetcode