Medium

314. Binary Tree Vertical Order Traversal

treebreadth-first-searchhash-table

解題說明

Binary Tree Vertical Order Traversal

題目描述：給定一棵二元樹，請依照「垂直行序」由左至右、由上至下輸出每一行的節點值。若兩個節點位於同一行（column）且同一層（row），則依照從左到右的順序排列。

例如，樹 [3,9,20,null,null,15,7] 的結構如下：

以垂直行來看：

column -1：9
column 0：3, 15
column 1：20
column 2：7

因此答案為 [[9],[3,15],[20],[7]]。

解題思路：本題的核心是為每個節點指派一個「欄編號（column index）」，根節點為 0，往左走 -1，往右走 +1。接著，同一欄的節點依照由上至下（BFS 的自然順序）排列，同層同欄則依左至右排列。

使用 BFS（廣度優先搜尋）搭配雜湊表（hash map）是最自然的做法：

用一個 queue 存放 (node, col) 的配對，初始放入 (root, 0)。
每次從 queue 取出節點，將其值加入 map[col] 的串列中。
若有左子節點，推入 (left, col - 1)；若有右子節點，推入 (right, col + 1)。
同時追蹤 minCol 和 maxCol，以便最後依序從最小欄到最大欄組合答案。

由於 BFS 本身是按層遍歷，同一欄內的節點自然符合「由上至下、同層由左至右」的要求，不需額外排序。這正是本題與 LC 987（需要座標排序）的關鍵差異所在。

C++ 解法

複雜度分析

時間複雜度：O(N)

每個節點恰好被訪問一次（BFS 每個節點入隊、出隊各一次），將節點值加入雜湊表也是 O(1) 的操作。最後從 minCol 到 maxCol 組合答案，欄數最多為 N（退化成鏈狀樹），因此總時間複雜度為 O(N)。

空間複雜度：O(N)

雜湊表 colMap 儲存所有 N 個節點的值，空間為 O(N)。
BFS 的 queue 在最壞情況（完全二元樹的最後一層）會同時持有 N/2 個節點，空間為 O(N)。
輸出的 result 同樣包含所有 N 個節點值，為 O(N)。

綜合以上，空間複雜度為 O(N)。

虛擬碼

1. If root is null, return empty result.
2. Initialize:
   - colMap: hash map from column index -> list of node values
   - queue of (node, col) pairs, starting with (root, 0)
   - minCol = +INF, maxCol = -INF
3. While queue is not empty:
   a. Dequeue (node, col).
   b. Append node.val to colMap[col].
   c. Update minCol = min(minCol, col), maxCol = max(maxCol, col).
   d. If node.left exists,  enqueue (node.left,  col - 1).
   e. If node.right exists, enqueue (node.right, col + 1).
4. For each column c from minCol to maxCol (inclusive):
   - Append colMap[c] to result.
5. Return result.

其他解法

方法一：DFS（深度優先搜尋）+ 排序

同樣可以用遞迴 DFS 為每個節點計算 (row, col) 座標，並將 (row, col, val) 存入雜湊表。遍歷完成後，按 col 分組，再對每組內部依 row 排序（若題目需要嚴格的列內排序）。

優點：程式碼結構直覺，適合同時記錄深度資訊。
缺點：需要額外的排序步驟（O(N log N)），且同層節點若欄相同，必須小心維護左右順序。對於本題（LC 314）而言，BFS 天然保證同層由左至右的順序，DFS 則不保證，因此 BFS 更為適合。

方法二：BFS + 有序映射（map<int, vector<int>>）

將 unordered_map 改用 C++ 的 map（紅黑樹，自動按 key 排序）。好處是省去最後追蹤 minCol/maxCol 再線性掃描的步驟，可直接用迭代器依序輸出。

時間複雜度：O(N log N)（每次插入 map 為 O(log N)）。
在 N 較小時實作更簡潔；在追求最優時間複雜度時，unordered_map + minCol/maxCol 是更好的選擇。

延伸思考

延伸思考

本題（LC 314）與 LC 987（Vertical Order Traversal of a Binary Tree）有何差異？ LC 314 規定「同行同列的節點依左至右排列」，BFS 的層序遍歷天然滿足此條件，無需排序。LC 987 則要求「同行同列的節點依節點值由小至大排列」，因此必須記錄每個節點的 (row, col) 座標並進行三鍵排序（col → row → val），不能單純使用 BFS 的輸出順序。
如果樹非常寬（欄數遠大於高度），如何優化空間使用？ 可考慮將 queue 改為只存 (node, col)，並用 minCol/maxCol 動態縮放結果陣列的索引（例如以 col - minCol 作為陣列下標）。若欄範圍已知或有界，可預先分配固定大小的陣列，避免 hash map 的額外開銷。
若輸入是 N 叉樹，如何調整演算法？ 將 BFS 中左右子節點的欄偏移推廣為：對第 i 個子節點（0-indexed），欄偏移設為 i - (childCount - 1) / 2，或依具體題意定義「最左子為 col - (k/2)、最右子為 col + (k/2)」（k 為子節點數）。核心的 BFS + 雜湊表框架無需改動。