---

[!info] related notes 算法面试题型 MOC 二叉树高频题

Binary Tree Zigzag Level-Order Traversal

LeetCode: https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/

思路

• 仍然是标准 BFS 按层处理。
• 第 level 层：
  • 偶数层：从左到右写入。
  • 奇数层：从右到左写入。

实现技巧：

• 预分配数组 level = new Array(size)，按位置写入：
  • idx = leftToRight ? i : (size - 1 - i)

Java Template

import java.util.*;

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.add(root);
        boolean leftToRight = true;

        while (!q.isEmpty()) {
            int size = q.size();
            Integer[] level = new Integer[size];
            for (int i = 0; i < size; i++) {
                TreeNode cur = q.poll();
                int idx = leftToRight ? i : (size - 1 - i);
                level[idx] = cur.val;
                if (cur.left != null) q.add(cur.left);
                if (cur.right != null) q.add(cur.right);
            }
            ans.add(Arrays.asList(level));
            leftToRight = !leftToRight;
        }
        return ans;
    }
}

Related

• 二叉树层序遍历
• 二叉树高频题