LeetCode 103 Binary Tree Zigzag Level Order Traversal：Java 實現 Z 字形層序遍歷

題目簡介

給定二叉樹，返回 Z 字形層序遍歷：第一層左→右，第二層右→左，交替進行。例：[3,9,20,null,null,15,7] → [[3],[20,9],[15,7]]。

解法一：隊列 + 反轉列表（冗餘）

用隊列層序遍歷，每層收集節點值到 ArrayList，若該層為右→左則在列表頭插入（或遍歷完反轉）。代碼較長。

解法二：隊列 + 索引插入（簡潔）

同樣層序遍歷，但根據層號奇偶決定插入位置：

• 奇數層（左→右）：list.add(val)。
• 偶數層（右→左）：list.add(0, val)。

無需額外棧或反轉，代碼極短。

代碼實現

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    int level = 1;
    while (!q.isEmpty()) {
        int size = q.size();
        List<Integer> cur = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            if (level % 2 == 1) cur.add(node.val);
            else cur.add(0, node.val);
            if (node.left != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
        res.add(cur);
        level++;
    }
    return res;
}

複雜度分析

時間 O(n)，空間 O(n)。add(0, val) 為 O(k) 但總體仍為 O(n)。