103. 二叉树的锯齿形层序遍历

核心逻辑

本解法采用 BFS（层序遍历） + 层号奇偶反转 的策略：

使用队列 Queue 进行标准层序遍历，一层一层处理。
定义一个变量 k 记录当前层数（从 1 开始计数）。
对于每一层，先按从左到右的顺序收集节点值。
如果是偶数层（k % 2 == 0），则反转该层的节点值列表，实现“从右往左”的效果。
如果是奇数层，直接加入结果。

时间复杂度为什么是 O(N) 而不是 O(N²)？

外层循环控制的是“层数”，内层循环控制的是“当前层的节点数”。
每个节点只会恰好进入一次内层循环，所有层的内层迭代次数之和 = 总节点数 N。
Collections.reverse() 反转每一层列表的总耗时也是 O(N)。
因此整体时间复杂度为 O(N)，不是 O(N²)。

代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int k = 0;  // 层数标记
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> integers = new ArrayList<>();
            k++;
            
            for (int i = 0; i < size; i++) {
                TreeNode t = queue.poll();
                integers.add(t.val);
                
                if (t.left != null) {
                    queue.add(t.left);
                }
                if (t.right != null) {
                    queue.add(t.right);
                }
            }
            
            // 锯齿形处理：偶数层反转
            if (k % 2 == 0) {
                Collections.reverse(integers);
                result.add(integers);
            } else {
                result.add(integers);
            }
        }
        return result;
    }
}

⏳ 复杂度分析