Medium

109. Convert Sorted List to Binary Search Tree

linked-listdivide-and-conquertreebinary-search-treebinary-tree

解題說明

Convert Sorted List to Binary Search Tree

題目描述：給定一個升序排列的單向鏈結串列，將其轉換為一棵高度平衡的二元搜尋樹（BST）。

解題思路：為了產生高度平衡的 BST，每次都需要選擇中間節點作為根。對鏈結串列而言，找中間節點可以用快慢指標。但更優雅的方式是模擬中序遍歷：先算出串列長度 n，然後遞迴地建樹。每次遞迴時先建左子樹，此時全域指標自然移到中間節點，取其值作為當前節點，再建右子樹。這樣每個節點只被訪問一次，時間為 O(n)。

C++ 解法

複雜度分析

時間複雜度：O(n) — 每個鏈結串列節點恰好被訪問一次來建立對應的樹節點。

空間複雜度：O(log n) — 遞迴深度為平衡 BST 的高度 O(log n)。

虛擬碼

1. Count total nodes n in the linked list
2. Define recursive function build(cur, lo, hi):
   a. If lo > hi, return null
   b. Compute mid = lo + (hi - lo) / 2
   c. Recursively build left subtree: left = build(cur, lo, mid - 1)
   d. Create node with cur's value, advance cur to cur.next
   e. Assign node.left = left
   f. Recursively build right subtree: node.right = build(cur, mid + 1, hi)
   g. Return node
3. Call build(head, 0, n - 1)

其他解法

快慢指標找中點 O(n log n)：每次用快慢指標找中間節點作為根，遞迴處理左右半段。每層遞迴需 O(n) 找中點，共 O(log n) 層，總時間 O(n log n)。實作直觀但效率較差。

先轉為陣列再建樹 O(n)：將鏈結串列值複製到陣列中，再用標準的有序陣列轉 BST 方法。時間 O(n) 但額外需要 O(n) 空間存陣列。

延伸思考

若輸入是雙向鏈結串列，能否利用額外資訊加速？
如何驗證建出的 BST 確實是高度平衡的？
能否在不計算長度的情況下完成建樹？

Convert Sorted List to Binary Search Tree — CaffeCode