對于算法題，按題型類別刷題才會更有成效，因此我這里在網上搜索并參考了下 “🔥 LeetCode 熱題 HOT 100” 的題型歸類，并在其基礎上做了一定的完善，希望能夠記錄自己的刷題歷程，有所收獲！點擊下發鏈接跳轉~??????

🔥 LeetCode 熱題 HOT 100【題型歸類匯總，助力刷題】

108. 將有序數組轉換為二叉搜索樹

??

給你一個整數數組?nums?，其中元素已經按?升序?排列，請你將其轉換為一棵?高度平衡?二叉搜索樹。

高度平衡?二叉樹是一棵滿足「每個節點的左右兩個子樹的高度差的絕對值不超過 1 」的二叉樹。

示例 1：

輸入：nums = [-10,-3,0,5,9]
輸出：[0,-3,9,-10,null,5]
解釋：[0,-10,5,null,-3,null,9] 也將被視為正確答案：

示例 2：

輸入：nums = [1,3]
輸出：[3,1]
解釋：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索樹。

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums?按?嚴格遞增?順序排列

思路：參考?LeetCode題解

• 二叉搜索樹BST 的【中序遍歷】是升序的，因此本題等同于根據中序遍歷的序列恢復二叉搜索樹

• 雖然我們可以以升序序列中的任一個元素作為根節點

• 但是因為本題要求【高度平衡】，因此我們需要選擇升序序列的【中間元素】作為根節點奧～

時間復雜度：O(n)，其中?n?是數組的長度。每個數字只訪問一次。

空間復雜度：O(logn)，其中 n?是數組的長度。空間復雜度不考慮返回值，因此空間復雜度主要取決于遞歸棧的深度，遞歸棧的深度是 O(log?n)。

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
// 參考題解：https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/solutions/313508/jian-dan-di-gui-bi-xu-miao-dong-by-sweetiee/?envType=study-plan-v2&envId=top-100-liked
// BST 的【中序遍歷】是升序的，因此本題等同于根據中序遍歷的序列恢復二叉搜索樹
// 雖然我們可以以升序序列中的任一個元素作為根節點
// 但是因為本題要求【高度平衡】，因此我們需要選擇升序序列的【中間元素】作為根節點奧～
func sortedArrayToBST(nums []int) *TreeNode {var dfs func(l, r int) *TreeNodedfs = func(l, r int) *TreeNode {if l > r {return nil}mid := l + (r-l)/2root := &TreeNode{}root.Val = nums[mid]root.Left = dfs(l, mid-1) // r向左，即中間位置移動root.Right = dfs(mid+1, r) // l向右，即向中間位置移動return root}return dfs(0, len(nums)-1)
}

題目擴展：

• 109. 有序鏈表轉換二叉搜索樹
• 將本題的數組換成了鏈表，做法完全一樣，不過鏈表無法像數組一樣直接索引到中間元素，鏈表找中間節點可以用快慢指針法，詳見：876. 鏈表的中間結點。