京公网安备11010502063487号在层序遍历的基础上，让方向交替：第 1 层从左到右，第 2 层从右到左，以此类推。做法是给标准 BFS 加一个方向标记，每层结束后判断是否需要反转、再切换方向。一个常见陷阱是：只写了"根据方向决定要不要反转"的判断，却忘了在每层结束后真正切换这个方向变量，导致它永远停在初始值，效果退化成普通层序遍历。本文用真实反例验证这个错误，给出正确写法、5 种语言实现，以及方向切换的分步演示。
本文只用自己的话概括题意，完整约束以官方页面为准。和层序遍历一样按层分组，但方向交替：第 1 层从左到右，第 2 层从右到左，第 3 层再从左到右，以此类推。一共 5 组用例，覆盖：官方示例、空树、单结点、完全二叉树、三结点简单树：
[3,9,20,null,null,15,7] → [[3], [20, 9], [15, 7]] [] → [] [1] → [[1]] [1,2,3,4,5,6,7] → [[1], [3, 2], [4, 5, 6, 7]] [1,2,3] → [[1], [3, 2]]
标准写法是在普通 BFS 层序遍历的基础上，用一个布尔变量记录当前方向，每层结束后取反。一个很容易犯的错误是：写好了"如果不是从左到右就反转这一层"的判断，但忘了在每层结束后真正切换这个方向变量——变量初始化成 True 后就再也没变过，判断永远走同一个分支，等价于普通层序遍历，完全没有"之字形"效果：
输入 [3,9,20,null,null,15,7]\n正确写法（每层后切换方向） → [[3], [20, 9], [15, 7]]\n陷阱写法（忘了切换方向） → [[3], [9, 20], [15, 7]]
第 2 层本该从右到左，输出 [20, 9]，但陷阱写法因为方向变量一直是 True，直接原样输出 [9, 20]，和普通层序遍历一模一样。用完全二叉树 [1,2,3,4,5,6,7] 再验证一次：
输入 [1,2,3,4,5,6,7]\n正确写法 → [[1], [3, 2], [4, 5, 6, 7]]\n陷阱写法 → [[1], [2, 3], [4, 5, 6, 7]]
在标准 BFS 层序遍历的基础上加一个方向标记：每层正常从左到右收集结点，如果当前方向是"从右到左"就把这一层的结果反转，再把方向标记取反，供下一层使用。时间 O(n)，空间 O(w)。Python、Java、Go、JavaScript、C++ 都是真实编译运行的，用同一组 5 个测试用例。
Python · 解法代码from collections import deque def zigzag_level_order(root): if root is None: return [] result = [] q = deque([root]) left_to_right = True while q: size = len(q) level = [] for _ in range(size): node = q.popleft() level.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) if not left_to_right: level.reverse() result.append(level) left_to_right = not left_to_right # 每层结束后切换方向 return result
$ python3 solution.py [3,9,20,null,null,15,7] → [[3], [20, 9], [15, 7]] [] → [] [1] → [[1]] [1,2,3,4,5,6,7] → [[1], [3, 2], [4, 5, 6, 7]] [1,2,3] → [[1], [3, 2]]
Java · 解法代码class Solution { public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) return result; Deque<TreeNode> q = new ArrayDeque<>(); q.add(root); boolean leftToRight = true; while (!q.isEmpty()) { int size = q.size(); List<Integer> level = new ArrayList<>(); for (int i = 0; i < size; i++) { TreeNode node = q.poll(); level.add(node.val); if (node.left != null) q.add(node.left); if (node.right != null) q.add(node.right); } if (!leftToRight) Collections.reverse(level); result.add(level); leftToRight = !leftToRight; // 每层结束后切换方向 } return result; } }
$ javac -d build Main.java && java -cp build Main [3,9,20,null,null,15,7] → [[3], [20, 9], [15, 7]] [] → [] [1] → [[1]] [1,2,3,4,5,6,7] → [[1], [3, 2], [4, 5, 6, 7]] [1,2,3] → [[1], [3, 2]]
Go · 解法代码func zigzagLevelOrder(root *TreeNode) [][]int { result := [][]int{} if root == nil { return result } q := []*TreeNode{root} leftToRight := true for len(q) > 0 { size := len(q) level := []int{} for i := 0; i < size; i++ { node := q[0] q = q[1:] level = append(level, node.Val) if node.Left != nil { q = append(q, node.Left) } if node.Right != nil { q = append(q, node.Right) } } if !leftToRight { for i, j := 0, len(level)-1; i < j; i, j = i+1, j-1 { level[i], level[j] = level[j], level[i] } } result = append(result, level) leftToRight = !leftToRight // 每层结束后切换方向 } return result }
$ go run solution.go [3,9,20,null,null,15,7] → [[3], [20, 9], [15, 7]] [] → [] [1] → [[1]] [1,2,3,4,5,6,7] → [[1], [3, 2], [4, 5, 6, 7]] [1,2,3] → [[1], [3, 2]]
JavaScript · 解法代码function zigzagLevelOrder(root) { const result = []; if (root === null) return result; let q = [root]; let leftToRight = true; while (q.length) { const size = q.length; const level = []; for (let i = 0; i < size; i++) { const node = q.shift(); level.push(node.val); if (node.left) q.push(node.left); if (node.right) q.push(node.right); } if (!leftToRight) level.reverse(); result.push(level); leftToRight = !leftToRight; // 每层结束后切换方向 } return result; }
$ node run.js [3,9,20,null,null,15,7] → [[3], [20, 9], [15, 7]] [] → [] [1] → [[1]] [1,2,3,4,5,6,7] → [[1], [3, 2], [4, 5, 6, 7]] [1,2,3] → [[1], [3, 2]]
C++ · 解法代码class Solution { public: vector<vector<int>> zigzagLevelOrder(TreeNode* root) { vector<vector<int>> result; if (!root) return result; queue<TreeNode*> q; q.push(root); bool leftToRight = true; while (!q.empty()) { int size = q.size(); vector<int> level; for (int i = 0; i < size; i++) { TreeNode* node = q.front(); q.pop(); level.push_back(node->val); if (node->left) q.push(node->left); if (node->right) q.push(node->right); } if (!leftToRight) reverse(level.begin(), level.end()); result.push_back(level); leftToRight = !leftToRight; // 每层结束后切换方向 } return result; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin [3,9,20,null,null,15,7] → [[3], [20, 9], [15, 7]] [] → [] [1] → [[1]] [1,2,3,4,5,6,7] → [[1], [3, 2], [4, 5, 6, 7]] [1,2,3] → [[1], [3, 2]]
共 5 组用例（含边界），以 Python 结果为基准逐组比对：\n Python 通过 5/5\n Java 通过 5/5\n Go 通过 5/5\n JavaScript 通过 5/5\n C++ 通过 5/5
Python 版本的 BFS 实现另外和一个独立写的 DFS 版本做了随机对拍：DFS 版按深度把结点分组（和普通层序遍历一样），遍历完成后再对深度是奇数的那些层分别反转。
随机对拍 30,000 组（结点数 0 到 10 的随机二叉树，值取 0-4），BFS 版与 DFS 版的结果全部一致，0 处不一致。
另外四种语言只在上面 5 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用官方示例 [3,9,20,null,null,15,7]：第 1 层从左到右，第 2 层收集顺序还是从左到右（9、20），但要在放进结果之前整体反转成 [20, 9]，第 3 层再切回从左到右。蓝色是本层正在处理的结点，绿色是已经处理完的结点。每一帧都是把上面的解法在这组输入上真实执行记录下来的。