樹的垂直結構（Vertical Order Traversal）圖解與演算法詳解

什麼是樹的垂直結構？

「垂直結構」指將二元樹節點依據 水平距離 分組：根節點 HD=0，左子節點 HD-1，右子節點 HD+1。相同 HD 的節點屬於同一條垂直線，按 HD 從小到大輸出，同 HD 內按層級（Top-to-Bottom）排序。

範例圖解

        1 (HD=0)
       / \
  2(-1)   3(+1)
  / \     / \
4(-2)5(0)6(0)7(+2)
  \       \
  8(+1)   9(+3)

垂直線分組：

• HD=-2：[4]
• HD=-1：[2]
• HD=0：[1, 5, 6] → 依層級序：1, 5, 6
• HD=+1：[3, 8] → 3, 8
• HD=+2：[7]
• HD=+3：[9]

最終輸出：4 2 1 5 6 3 8 7 9

演算法核心（BFS + Map）

// Java 參考實作
public List> verticalOrder(TreeNode root) {
    Map> cols = new TreeMap<>(); // 自動按 HD 排序
    Queue> q = new LinkedList<>();
    if (root != null) q.offer(new Pair<>(root, 0));

    while (!q.isEmpty()) {
        Pair p = q.poll();
        TreeNode node = p.getKey();
        int hd = p.getValue();
        cols.computeIfAbsent(hd, k -> new ArrayList<>()).add(node.val);
        if (node.left != null) q.offer(new Pair<>(node.left, hd - 1));
        if (node.right != null) q.offer(new Pair<>(node.right, hd + 1));
    }
    return new ArrayList<>(cols.values());
}

關鍵點：
✅ 使用 TreeMap 自動維護 HD 順序
✅ BFS 保證同 HD 節點按層級順序入列
✅ 時間/空間複雜度皆為 O(N)

常見變體

• LeetCode 987 Vertical Order Traversal：同 HD 同層需按節點值排序 → 改用 Map>> 記錄 (HD, Level) → 值列表再排序。
• 底部視圖：只取每條垂直線最底層節點 → BFS 時直接覆蓋 map[hd] = node.val。