LeetCode 107: 二叉樹自底向上的層序遍歷

關鍵代碼片段

public List> levelOrderBottom(TreeNode root) {
    List> res = new LinkedList<>();
    if (root == null) return res;
    Queue q = new LinkedList<>();
    q.offer(new TreeNodeWithDepth(root, 1));
    int lastLevel = 1;
    List curLevel = new ArrayList<>();
    while (!q.isEmpty()) {
        TreeNodeWithDepth nd = q.poll();
        if (nd.depth > lastLevel) {
            res.add(0, curLevel); // 關鍵：頭插
            curLevel = new ArrayList<>();
            lastLevel = nd.depth;
        }
        curLevel.add(nd.treeNode.val);
        if (nd.treeNode.left != null)
            q.offer(new TreeNodeWithDepth(nd.treeNode.left, nd.depth + 1));
        if (nd.treeNode.right != null)
            q.offer(new TreeNodeWithDepth(nd.treeNode.right, nd.depth + 1));
    }
    if (!curLevel.isEmpty()) res.add(0, curLevel);
    return res;
}

static class TreeNodeWithDepth {
    TreeNode treeNode; int depth;
    TreeNodeWithDepth(TreeNode n, int d) { treeNode = n; depth = d; }
}

為什麼用 LinkedList？

• ArrayList.add(0, x) 需移動所有元素，O(n)；
• LinkedList.add(0, x) 僅修改頭指針，O(1)。
• 層數最多 O(h)，h ≤ n，用 LinkedList 總時間 O(n)。

替代方案：正序收集後反轉

List> res = new ArrayList<>();
// 正常 BFS，res.add(curLevel);
Collections.reverse(res); // 最後整體反轉
return res;

兩種寫法時間復雜度均為 O(n)，空間 O(n)。頭插法省去最後反轉步驟，代碼更直觀。

複雜度分析

• 時間：O(n) —— 每個節點入隊出隊各一次。
• 空間：O(n) —— 隊列與結果列表共同存儲所有節點值。

總結

本題是層序遍歷的簡單變體。核心技巧：使用 LinkedList 實現 O(1) 頭插，或正序收集後整體反轉。兩種思路均可，掌握 BFS 模板與列表操作細節即可輕鬆解決。