日期：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()
