k652

#include <bits/stdc++.h>
using namespace std;


int main() {
    int n;
    cin >> n;
    vector<int> post_order(n);
    for (int i = 0; i < n; i++) {
        cin >> post_order[i];
    }

    
    map<int, int> parent_map;
    stack<int> st;

    // 根據後序走訪序列構建 BST
    parent_map[post_order[n - 1]] = -1; 
    st.push(post_order[n - 1]);

    for (int i = n - 2; i >= 0; i--) {
        int current = post_order[i];
        int parent = -1;

        // 調整堆疊以找到當前節點的父節點
        while (!st.empty() && st.top() > current) {
            parent = st.top();
            st.pop();
        }

        if (parent == -1) {
            parent = st.top();
        }

        parent_map[current] = parent;
        st.push(current);
    }

   
    for (const auto &entry : parent_map) {
        cout << entry.first << " " << entry.second << '\n';
    }

    return 0;
}
Select a repo