HDU 5444 Elven Postman：二叉搜索樹構建與路徑查詢

HDU 5444 Elven Postman：二叉搜索樹構建與路徑查詢

題目背景

精靈住在樹上，樹的分叉至多兩條（東/西），恰似二叉樹。房間編號規則：從最東端到最西端依次編號（東邊房間更貴，能看日出）。根節點處寫著一個序列，記錄遍歷順序：先走到最東端房間，沿途記錄所有遇到的房間；再找下一個未訪問的最東端房間，記錄沿途未訪問房間，直到全部訪問完畢。給定這個序列，詢問從根到某房間的路徑（E=東/左，W=西/右）。

關鍵洞察

給定的序列正是二叉搜索樹的先序遍歷！
- 第一個數是根。
- 後續數依次插入：小於當前節點去左子樹（東），大於去右子樹（西）。
- 構建出的 BST 中序遍歷即為 1..n 排序，符合「東到西編號」規則。
- 查詢路徑：從根開始，目標值小於當前節點輸出 'E' 走左，大於輸出 'W' 走右，相等結束。

算法流程

1. 讀入序列第一個值建立根節點。
2. 依次插入其餘值構建 BST（遞歸或迭代）。
3. 對每個查詢，從根查找目標值，輸出路徑字符串。

複雜度

• 構建：O(n²) 最壞（退化鏈表），n≤1000 可接受。平均 O(n log n)。
• 查詢：O(h) ≤ O(n)，q 次查詢總 O(qn)。

參考代碼 (C++)

#include <iostream>
#include <cstdio>
using namespace std;

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

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

void queryPath(Node *root, int x) {
    if (root->val == x) { puts(""); return; }
    if (x < root->val) { putchar('E'); queryPath(root->left, x); }
    else { putchar('W'); queryPath(root->right, x); }
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        int first; scanf("%d", &first);
        Node *root = new Node(first);
        for (int i = 1; i < n; i++) {
            int x; scanf("%d", &x);
            insert(root, x);
        }
        int q; scanf("%d", &q);
        while (q--) {
            int x; scanf("%d", &x);
            queryPath(root, x);
        }
        // 實際比賽可不釋放內存，程序結束自動回收
    }
    return 0;
}

樣例解析

輸入：
2
4
2 1 4 3
3
1 2 3
6
6 5 4 3 2 1
1
1

輸出：
E
W
E
EEEEE

第一棵樹：根 2，左 1，右 4，4 的左 3。查詢 1→E，2→(空行)，3→W E（輸出 WE）。