HDU 5444 Elven Postman 解題報告：BST 構建與路徑查詢

題目大意

給定 n 個節點值，按輸入順序構建二叉搜索樹（BST）：第一個值為根，後續值 < 小於根去左子樹，大於等於去右子樹）。
對 q 個查詢，輸出從根到目標節點的路徑：E（東/左）、W（西/右），根節點輸出空行。

解法：直接構建 BST + 遞歸查找

數據範圍 n ≤ 1000，直接 O(n²) 構建完全足夠。

核心代碼

struct Node {
    int val;
    Node *left, *right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

void insert(Node* &root, int val) {
    if (!root) { root = new Node(val); return; }
    if (val < root->val) insert(root->left, val);
    else insert(root->right, val);
}

void printPath(Node* root, int target) {
    if (!root) return;
    if (root->val == target) { cout << '\n'; return; }
    if (target < root->val) {
        cout << 'E';
        printPath(root->left, target);
    } else {
        cout << 'W';
        printPath(root->right, target);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        Node* root = nullptr;
        for (int i = 0, x; i < n; i++) {
            cin >> x;
            insert(root, x);
        }
        int q; cin >> q;
        while (q--) {
            int x; cin >> x;
            printPath(root, x);
        }
        // 釋放記憶體（選做）
    }
    return 0;
}

樣例追蹤

輸入：4\n2 1 4 3

構建過程：

    2
   / \
  1   4
     /
    3

查詢 1：E（根→左）
查詢 2：空行（根）
查詢 3：WE（根→右→左）

複雜度

• 構建：O(n²) 最壞（退化鏈），平均 O(n log n)
• 查詢：O(h)，h 為樹高
• 空間：O(n)

優化備註

若 n 較大（如 1e5），可用笛卡尔樹/平衡樹 O(n log n) 構建，但本題 n ≤ 1000 無需優化。

易錯點

1. 相等值去右子樹：題目「小於去左，大於等於去右」
2. 多測試用例：每輪重新構建樹，釋放舊節點避免記憶體洩漏
3. 根節點輸出空行：cout << '\n' 而非空字串

總結

裸 BST 構建 + 路徑查詢模板題。關鍵：

• 按輸入順序插入構建 BST
• 遞歸查找並輸出方向
• 注意相等值處理與根節點特判