ZeroJudge K652: 二元搜尋樹復原 (BST)

題目敘述

每筆測資第一行有一個正整數N，第二行有N個整數，代表這N個數字進行二元搜尋數排序後輸出的結果。要求輸出每個數字在二元搜尋數當中的上一個節點是哪個數字，如果為跟節點的話則輸出-1 (輸出格式請參照範例輸入/輸出)。

範例輸入

8

2 1 6 3 15 19 12 7

範例輸出

1 3

2 1

3 7

6 3

7 -1

12 7

15 19

19 12

解題思路

本題可以參照D526的解題方式，只是從最右邊到最左邊建立二元搜尋樹，當把資料塞到struct裡時，因為二元搜尋樹的資料不是連續的整數，所以可以使用Map把目前數字的上一個節點存起來。當要輸出時，只需使用For迴圈並使用 (auto it:MAP) 來做輸出，當使用auto it:MAP的時候it會變成一個pair的型態，所以只需輸出it.first和it.second即可。本題如果使用endl來輸出的時候可能會遇到TLE的情況出現，所以可以使用cout << "\n"或是scanf/printf來加速。

解題程式碼如下 (僅供參考)：

#include <vector>
#include <map>
#include <stdio.h>
using namespace std;

struct Node {
    int value;
    struct Node *left;
    struct Node *right;
};

int main() {
    int N;
    while (scanf("%d", &N) != EOF)
    {
        map<int, int>MAP;
        vector<int>a;
        for (int i = 0; i<N; i++)
        {
            int tmp;
            scanf("%d", &tmp);
            a.push_back(tmp);
        }
        //int a[] = {8,4,2,3,5,1,9,6};
        Node* sean = new Node();
        sean->value = a[a.size()-1];
        Node* root;
        for(int i = N-2; i >= 0; i--) {
            root = sean;
            Node* p = new Node();
            p->value = a[i];
            while(true) {
                if(root->value < a[i]) {
                    if(root->right == nullptr) {
                        MAP[a[i]] = root->value;
                        root->right = p;
                        break;
                    } else {
                        root = root->right;
                    }
                }
                else if(root->value > a[i]) {
                    if(root->left == nullptr) {
                        MAP[a[i]] = root->value;
                        root->left = p;
                        break;
                    } else {
                        root = root->left;
                    }
                }
            }
        }
        MAP[a[a.size()-1]] = -1;
        for (auto it:MAP)
        {
            printf("%d %d\n", it.first, it.second);
        }
    }
}