POJ

POJ1577 Falling Leaves

題目連結

  • 題意：給定一顆二元搜索樹，依序給葉節點的值、葉節點祖先的值、葉節點祖先的祖先的值。要你給出這棵樹的前序順序。
  • 題解：這題要從最上層(最晚給的資料)開始插入二元樹，這樣就能還原出二元搜索樹。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    #pragma GCC optimize(2)
    #include <cstring>
    #include <iostream>
    #include <stack>
    #include <string>
    #include <vector>

    using namespace std;
    const int INF = 1e9;
    const int MXN = 1e6 + 5;
    const int MXV = 0;
    #define MP make_pair
    #define PB push_back
    #define F first
    #define S second
    #define FOR(i, L, R) for (int i = L; i != (int)R; ++i)
    #define FORD(i, L, R) for (int i = L; i != (int)R; --i)
    #define IOS                                                                    \
        cin.tie(NULL);                                                             \
        cout.tie(NULL);                                                            \
        ios_base::sync_with_stdio(false);
    struct Node
    {
        char val;
        Node *Lc, *Rc;
        Node() : Lc(NULL), Rc(NULL) {}
    };

    Node *insert(Node *node, char val)
    {
        if (node == NULL)
        {
            node = new Node();
            node->val = val;
        }
        else if (val < node->val)
        {
            node->Lc = insert(node->Lc, val);
        }
        else
        {
            node->Rc = insert(node->Rc, val);
        }
        return node;
    }

    void dfs(Node *node)
    {
        if (node == NULL)
        {
            return;
        }
        cout << node->val;
        dfs(node->Lc);
        dfs(node->Rc);
    }

    int main()
    {
        IOS;
        string s;
        stack<string> st;
        while (cin >> s)
        {
            do
            {
                st.push(s);
            } while (cin >> s, isalpha(s[0]));
            Node *root = NULL;
            while (!st.empty())
            {
                s = st.top();
                st.pop();
                FOR(i, 0, s.size()) { root = insert(root, s[i]); }
            }
            dfs(root);
            cout << '\n';
        }
    }

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)

Recommended Posts