MediumRating 1563

1008. Construct Binary Search Tree from Preorder Traversal

arraystacktreebinary-search-treemonotonic-stackbinary-tree

在 LeetCode 上作答 ↗

解題說明

Construct Binary Search Tree from Preorder Traversal

題目描述：給定一個 BST 的前序遍歷結果，重建該二元搜尋樹。

解題思路：

遞迴 + 上界法：前序遍歷的第一個元素是根節點。利用 BST 的性質，所有小於根的值在左子樹，大於根的值在右子樹。
維護一個全域索引和一個上界（bound）。每次遞迴時，如果當前值 <= bound，就建立節點。
先遞迴建立左子樹（上界為當前節點值），再遞迴建立右子樹（上界為父節點傳入的 bound）。
這個方法在一次遍歷中完成建樹，時間和空間都是最優的。

C++ 解法

複雜度分析

時間複雜度：O(n) — 每個節點只處理一次

空間複雜度：O(n) — 遞迴堆疊深度（最壞情況為偏斜樹）

虛擬碼

1. Initialize global index = 0
2. build(preorder, bound):
   a. If index >= n or preorder[index] > bound: return null
   b. Create node with value preorder[index], increment index
   c. node.left = build(preorder, node.val)  // left subtree values < node
   d. node.right = build(preorder, bound)    // right subtree values < parent's bound
   e. Return node
3. Call build(preorder, INT_MAX) as root has no upper bound

其他解法

遞迴 + 二分搜尋分割：對每個根節點，用二分搜尋找出左子樹和右子樹在前序遍歷中的分界點。左子樹是值 < root 的部分，右子樹是值 > root 的部分。時間複雜度 O(n log n)。
單調棧方法：用棧模擬建樹過程。從左到右遍歷前序陣列，維護一個遞減棧。當遇到比棧頂大的值時，不斷彈出棧頂（找到正確的父節點），新節點作為右子節點插入。時間複雜度 O(n)。

延伸思考

如果給定的是後序遍歷而非前序遍歷，如何修改算法？
如果給定的前序遍歷結果不合法（不能構成 BST），如何檢測？
能否同時給定前序和中序遍歷，用更通用的方法重建任意二元樹？

Construct Binary Search Tree from Preorder Traversal — CaffeCode