題目描述: 給定一個 BST 的前序遍歷結果,重建該二元搜尋樹。
解題思路:
時間複雜度: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)。