LeetCode 103: Binary Tree Zigzag Level Order Traversal (BFS + Direction Toggle)
LeetCode 103TreeBFSQueueToday we solve LeetCode 103 - Binary Tree Zigzag Level Order Traversal.
Source: https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
English
Problem Summary
Given the root of a binary tree, return the level order traversal of node values, but alternate direction at each level: left-to-right, then right-to-left, and so on.
Key Insight
Standard BFS already gives nodes grouped by level. We only need an extra boolean leftToRight to decide where each value is placed inside the current level array.
Brute Force and Limitations
One brute way: do normal BFS level order first, then reverse every odd-indexed level. This works but introduces an extra reverse pass and avoids direct placement.
Optimal Algorithm Steps
1) If root is null, return empty list.
2) Push root into queue.
3) For each BFS level, allocate level[size].
4) Pop nodes, compute insert index:
- i if leftToRight
- size - 1 - i otherwise
5) Push children into queue.
6) Append level to answer and flip direction.
Complexity Analysis
Time: O(n), each node is enqueued/dequeued once.
Space: O(n), queue plus output.
Common Pitfalls
- Reversing wrong levels due to direction flag update timing.
- Appending children in zigzag order (unnecessary and error-prone).
- Forgetting to pre-size level array when writing by index.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) return ans;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
boolean leftToRight = true;
while (!q.isEmpty()) {
int size = q.size();
Integer[] level = new Integer[size];
for (int i = 0; i < size; i++) {
TreeNode node = q.poll();
int idx = leftToRight ? i : (size - 1 - i);
level[idx] = node.val;
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
ans.add(Arrays.asList(level));
leftToRight = !leftToRight;
}
return ans;
}
}func zigzagLevelOrder(root *TreeNode) [][]int {
if root == nil {
return [][]int{}
}
q := []*TreeNode{root}
leftToRight := true
ans := [][]int{}
for len(q) > 0 {
size := len(q)
level := make([]int, size)
for i := 0; i < size; i++ {
node := q[0]
q = q[1:]
idx := i
if !leftToRight {
idx = size - 1 - i
}
level[idx] = node.Val
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
ans = append(ans, level)
leftToRight = !leftToRight
}
return ans
}class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> ans;
if (!root) return ans;
queue<TreeNode*> q;
q.push(root);
bool leftToRight = true;
while (!q.empty()) {
int size = q.size();
vector<int> level(size);
for (int i = 0; i < size; i++) {
TreeNode* node = q.front(); q.pop();
int idx = leftToRight ? i : (size - 1 - i);
level[idx] = node->val;
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
ans.push_back(level);
leftToRight = !leftToRight;
}
return ans;
}
};from collections import deque
class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
q = deque([root])
left_to_right = True
ans = []
while q:
size = len(q)
level = [0] * size
for i in range(size):
node = q.popleft()
idx = i if left_to_right else size - 1 - i
level[idx] = node.val
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
ans.append(level)
left_to_right = not left_to_right
return ansvar zigzagLevelOrder = function(root) {
if (!root) return [];
const q = [root];
let leftToRight = true;
const ans = [];
while (q.length) {
const size = q.length;
const level = new Array(size);
for (let i = 0; i < size; i++) {
const node = q.shift();
const idx = leftToRight ? i : (size - 1 - i);
level[idx] = node.val;
if (node.left) q.push(node.left);
if (node.right) q.push(node.right);
}
ans.push(level);
leftToRight = !leftToRight;
}
return ans;
};中文
题目概述
给定二叉树根节点，按层序遍历返回节点值；但每一层的输出方向需要交替：第一层从左到右，第二层从右到左，依次往复。
核心思路
按层 BFS 本身就能分层。我们只需要一个方向标记 leftToRight，决定当前层写入下标：顺序写或反向写。
暴力解法与不足
先做普通层序遍历，再把奇数层反转。实现简单，但多了一次反转步骤，不如在遍历时直接按目标下标写入高效直观。
最优算法步骤
1）空树返回空数组。
2）根节点入队。
3）每层取队列长度 size，创建定长数组 level。
4）依次出队并计算写入位置：leftToRight ? i : size-1-i。
5）左右孩子照常入队（不需要按锯齿顺序入队）。
6）当前层加入答案后翻转方向标记。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(n)（队列与结果）。
常见陷阱
- 方向标记翻转时机写错，导致层方向整体偏移。
- 误以为孩子入队顺序也要交替，结果逻辑变乱。
- 未预分配当前层数组却按下标写入。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) return ans;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
boolean leftToRight = true;
while (!q.isEmpty()) {
int size = q.size();
Integer[] level = new Integer[size];
for (int i = 0; i < size; i++) {
TreeNode node = q.poll();
int idx = leftToRight ? i : (size - 1 - i);
level[idx] = node.val;
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
ans.add(Arrays.asList(level));
leftToRight = !leftToRight;
}
return ans;
}
}func zigzagLevelOrder(root *TreeNode) [][]int {
if root == nil {
return [][]int{}
}
q := []*TreeNode{root}
leftToRight := true
ans := [][]int{}
for len(q) > 0 {
size := len(q)
level := make([]int, size)
for i := 0; i < size; i++ {
node := q[0]
q = q[1:]
idx := i
if !leftToRight {
idx = size - 1 - i
}
level[idx] = node.Val
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
ans = append(ans, level)
leftToRight = !leftToRight
}
return ans
}class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> ans;
if (!root) return ans;
queue<TreeNode*> q;
q.push(root);
bool leftToRight = true;
while (!q.empty()) {
int size = q.size();
vector<int> level(size);
for (int i = 0; i < size; i++) {
TreeNode* node = q.front(); q.pop();
int idx = leftToRight ? i : (size - 1 - i);
level[idx] = node->val;
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
ans.push_back(level);
leftToRight = !leftToRight;
}
return ans;
}
};from collections import deque
class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
q = deque([root])
left_to_right = True
ans = []
while q:
size = len(q)
level = [0] * size
for i in range(size):
node = q.popleft()
idx = i if left_to_right else size - 1 - i
level[idx] = node.val
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
ans.append(level)
left_to_right = not left_to_right
return ansvar zigzagLevelOrder = function(root) {
if (!root) return [];
const q = [root];
let leftToRight = true;
const ans = [];
while (q.length) {
const size = q.length;
const level = new Array(size);
for (let i = 0; i < size; i++) {
const node = q.shift();
const idx = leftToRight ? i : (size - 1 - i);
level[idx] = node.val;
if (node.left) q.push(node.left);
if (node.right) q.push(node.right);
}
ans.push(level);
leftToRight = !leftToRight;
}
return ans;
};
Comments