a296. TOI 2022/12 潛力組：二元搜尋樹復原

題目描述

一棵非空的二元搜尋樹中，每個節點存有一個整數，所有節點的值都不相同。每個節點最多有一個左子節點與一個右子節點，而且必須符合下列規則：

• 左子樹內的所有值都小於目前節點的值。
• 右子樹內的所有值都大於目前節點的值。
• 每棵子樹也遵守相同的規則，左右子樹的位置不能互換。

對這棵樹進行後序走訪時，先走訪左子樹，再走訪右子樹，最後記錄目前節點的值；不存在的子樹直接略過。

現在給你這棵樹的後序走訪結果。請還原各節點的父子關係，找出每個節點的父節點。根節點沒有父節點，以 -1 表示。

輸入格式

第一行是一個正整數 N，表示節點數量。 第二行包含 N 個以空白分隔的正整數 P₁、P₂、…、Pₙ，依序為後序走訪所記錄的值。

• 1 ≤ N ≤ 200000
• 1 ≤ Pᵢ ≤ 1000000000
• 所有 Pᵢ 互不相同；此序列來自一棵符合題意的二元搜尋樹。

輸出格式

輸出 N 行，每行包含兩個以空白分隔的整數 U 與 F，表示值為 U 的節點，其父節點的值為 F。若 U 是根節點，F 為 -1。

請按照 U 由小到大的順序輸出，每個節點恰好出現一次。

來源

TOI 2022 年 12 月潛力組〈二元搜尋樹復原（BST）〉。本題敘以自寫文字重述；公開範例與隱藏測資均另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202212/BST.pdf