ZeroJudge 解題筆記：k652. 二元搜尋樹復原 (BST)

作者：王一哲
日期：2026年4月7日


ZeroJudge 題目連結：k652. 二元搜尋樹復原 (BST)
原題連結

解題想法

自訂類別 Node 及 BST，在 BST 之中用遞迴從根節點開始往下找插入新節點的位置，題目的輸出方式是中序走訪，但是同時要印出父節點的值。詳細的說明已經寫在程式碼的註解之中。

Python 程式碼

使用時間約為 0.6 s，記憶體約為 61.8 MB，通過測試。

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

    def insert(self, val, node = None):
        # 如果 node 為 None，設為 self.root，如果 self.root 是空的，新增 self.root
        if node is None:
            node = self.root
            if self.root is None:
                self.root = Node(val)
                return
        # 如果 val 較小，放到 node.left，如果 node.left 是空的，新增 node.left
        # 如果已經有 node.left，遞迴，試著放到 node.left 之下
        if val < node.val:
            if not node.left:
                node.left = Node(val)
            else:
                self.insert(val, node.left)
        # 如果 val 較大，放到 node.right，如果 node.right 是空的，新增 node.right
        # 如果已經有 node.right，遞迴，試著放到 node.right 之下
        else:
            if not node.right:
                node.right = Node(val)
            else:
                self.insert(val, node.right)

    def inorder(self, node = None, parent = -1):
        # 中序走訪，順序為 left, root, right
        # 如果 node 為 None，設為 self.root
        if node is None:
            node = self.root
        # 如果有 node.left，遞迴，代入 node.left 及 node.val
        if node.left:
            self.inorder(node.left, node.val)
        # 印出 node.val 及父節點的值；如果是根節點，parent 的值為 -1
        print(node.val, parent)
        # 如果有 node.right，遞迴，代入 node.right 及 node.val
        if node.right:
            self.inorder(node.right, node.val)

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        # 測資給的順序是後序走訪，最後一個是根節點，倒序加入 bst 之中
        arr = list(map(int, data[ptr:ptr+n]))
        ptr += n
        bst = BST()
        for u in arr[::-1]:
            bst.insert(u)
        bst.inorder()

if __name__ == "__main__":
    solve()

C++ 程式碼

使用時間約為 38 ms，記憶體約為 9.5 MB，通過測試。

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

struct Node {
    int val;
    Node* left;
    Node* right;

    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

class BST {
private:
    void insertHelper(int x, Node* node) {
        // 如果 x 較小，放到 node->left，如果 node->left 是空的，新增 node->left
        // 如果已經有 node->left，遞迴，試著放到 node->left 之下
        if (x < node->val) {
            if (node->left == nullptr) {
                node->left = new Node(x);
            } else {
                insertHelper(x, node->left);
            }
        } else {
            // 如果 x 較大，放到 node->right，如果 node->right 是空的，新增 node->right
            // 如果已經有 node->right，遞迴，試著放到 node->right 之下
            if (node->right == nullptr) {
                node->right = new Node(x);
            } else {
                insertHelper(x, node->right);
            }
        }
    }

    void inorderHelper(Node* node, int parent = -1) {
        // 中序走訪，順序為 left, root, right
        // 如果有 node->left，遞迴，代入 node->left 及 node->val
        if (node->left != nullptr) {
            inorderHelper(node->left, node->val);
        }
        // 印出 node->val 及父節點的值；如果是根節點，parent 的值為 -1
        printf("%d %d\n", node->val, parent);
        // 如果有 node->right，遞迴，代入 node->right 及 node->val
        if (node->right != nullptr) {
            inorderHelper(node->right, node->val);
        }
    }

public:
    Node *root;

    BST() : root(nullptr) {}
    
    void insert(int x) {
        if (root == nullptr){
            root = new Node(x);
        } else {
            insertHelper(x, root);
        }
    }

    void inorder() {
        if (root != nullptr) {
            inorderHelper(root);
        }
    }
};

int main() {
    int n;
    while(scanf("%d", &n) != EOF) {
        // 測資給的順序是後序走訪，最後一個是根節點，倒序加入 bst 之中
        vector<int> arr(n);
        for(int i=0; i<n; i++) {
            scanf("%d", &arr[i]);
        }
        BST bst;
        for(auto it = arr.crbegin(); it != arr.crend(); it++) {
            bst.insert(*it);
        }
        bst.inorder();
    }
    return 0;
}