LeetCode 二叉樹層序遍歷 II：自底向上的 BFS 兩種實現

題目需求

給定二叉樹，返回自底向上的層序遍歷結果。即葉子層在前，根節點在後。每層內左到右。

解法一：逐層隊列 + 結果反轉

標準 BFS：隊列存儲當前層節點，處理完後將子節點入隊。收集每層值到 list，最後反轉。

public List<List<Integer>> levelOrderBottom(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    List<List<Integer>> levels = new ArrayList<>();
    
    while (!queue.isEmpty()) {
        List<Integer> levelVals = new ArrayList<>();
        List<TreeNode> nextLevel = new ArrayList<>();
        
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            levelVals.add(node.val);
            if (node.left != null) nextLevel.add(node.left);
            if (node.right != null) nextLevel.add(node.right);
        }
        levels.add(levelVals);
        queue.addAll(nextLevel);
    }
    
    for (int i = levels.size() - 1; i >= 0; i--) result.add(levels.get(i));
    return result;
}

解法二：單隊列 + 層級計數器（更優雅）

用 currentLevel 和 nextLevel 計數器控制換行，無需額外列表存儲節點。

public List<List<Integer>> levelOrderBottom(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    List<List<Integer>> levels = new ArrayList<>();
    List<Integer> level = new ArrayList<>();
    
    int currentLevel = 1, nextLevel = 0;
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        currentLevel--;
        level.add(node.val);
        
        if (node.left != null) { queue.offer(node.left); nextLevel++; }
        if (node.right != null) { queue.offer(node.right); nextLevel++; }
        
        if (currentLevel == 0) {
            levels.add(level);
            level = new ArrayList<>();
            currentLevel = nextLevel;
            nextLevel = 0;
        }
    }
    
    for (int i = levels.size() - 1; i >= 0; i--) result.add(levels.get(i));
    return result;
}

複雜度與比較

解法二是面試中的優選寫法，展現對 BFS 流程控制的深度理解。