原題鏈接🔗：將有序數(shù)組轉(zhuǎn)換為二叉搜索樹(shù)
難度：簡(jiǎn)單??

題目

給你一個(gè)整數(shù)數(shù)組 nums ，其中元素已經(jīng)按 升序 排列，請(qǐng)你將其轉(zhuǎn)換為一棵 平衡 二叉搜索樹(shù)。

示例 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] 都是高度平衡二叉搜索樹(shù)。

提示：

• 1 <= nums.length <= 10⁴
• -10⁴ <= nums[i] <= 10⁴
• nums 按 嚴(yán)格遞增 順序排列

平衡二叉搜索樹(shù)

• 平衡二叉搜索樹(shù)（Balanced Binary Search Tree，簡(jiǎn)稱BBST）是一種特殊的二叉搜索樹(shù)，它在保持二叉搜索樹(shù)的所有性質(zhì)的同時(shí)，還保證了樹(shù)的高度盡可能地小。這通常通過(guò)在插入和刪除操作后重新平衡樹(shù)來(lái)實(shí)現(xiàn)，以確保樹(shù)的任何兩個(gè)子樹(shù)的高度差不會(huì)超過(guò)1。

• 平衡二叉搜索樹(shù)的一個(gè)常見(jiàn)實(shí)現(xiàn)是AVL樹(shù)，它是一種自平衡的二叉搜索樹(shù)，其名稱來(lái)源于其發(fā)明者Adelson-Velsky和Landis。AVL樹(shù)在每次插入或刪除操作后，都會(huì)進(jìn)行必要的旋轉(zhuǎn)操作來(lái)保持樹(shù)的平衡。

• AVL樹(shù)的平衡操作包括四種基本的旋轉(zhuǎn)：

  • 左旋（Left Rotation）：當(dāng)節(jié)點(diǎn)的右子樹(shù)比左子樹(shù)高時(shí)，進(jìn)行左旋來(lái)減少樹(shù)的高度。
  • 右旋（Right Rotation）：當(dāng)節(jié)點(diǎn)的左子樹(shù)比右子樹(shù)高時(shí)，進(jìn)行右旋來(lái)減少樹(shù)的高度。
  • 左右旋（Left-Right Rotation）：當(dāng)節(jié)點(diǎn)的左子樹(shù)的右子樹(shù)比左子樹(shù)高時(shí)，首先對(duì)左子樹(shù)進(jìn)行右旋，然后對(duì)節(jié)點(diǎn)進(jìn)行左旋。
  • 右左旋（Right-Left Rotation）：當(dāng)節(jié)點(diǎn)的右子樹(shù)的左子樹(shù)比右子樹(shù)高時(shí)，首先對(duì)右子樹(shù)進(jìn)行左旋，然后對(duì)節(jié)點(diǎn)進(jìn)行右旋。

• AVL樹(shù)的每個(gè)節(jié)點(diǎn)除了存儲(chǔ)值和指向左右子節(jié)點(diǎn)的指針外，還存儲(chǔ)了一個(gè)平衡因子（balance factor），通常是左子樹(shù)高度和右子樹(shù)高度的差值。節(jié)點(diǎn)的平衡因子只能是-1、0或1。

題解

遞歸法

1. 解題思路：

將一個(gè)有序數(shù)組轉(zhuǎn)換為二叉搜索樹(shù)（BST）的解題思路基于二叉搜索樹(shù)的性質(zhì)：左子樹(shù)上所有節(jié)點(diǎn)的值 < 根節(jié)點(diǎn)的值 < 右子樹(shù)上所有節(jié)點(diǎn)的值。對(duì)于一個(gè)有序數(shù)組，我們可以利用數(shù)組的有序性來(lái)快速確定根節(jié)點(diǎn)和左右子樹(shù)的劃分點(diǎn)。

以下是解題步驟：

• 確定根節(jié)點(diǎn)：對(duì)于有序數(shù)組，中間元素（數(shù)組長(zhǎng)度的一半）是一個(gè)很好的根節(jié)點(diǎn)候選，因?yàn)樗梢院芎玫鼐S持左右子樹(shù)的大小平衡。

• 遞歸構(gòu)建左右子樹(shù)：使用數(shù)組下標(biāo)來(lái)劃分，左子樹(shù)包含從數(shù)組開(kāi)始到根節(jié)點(diǎn)前的部分，右子樹(shù)包含從根節(jié)點(diǎn)的下一個(gè)元素到數(shù)組末尾的部分。

• 遞歸終止條件：當(dāng)子數(shù)組為空時(shí)，返回null。

• 構(gòu)建樹(shù)：對(duì)于每個(gè)子數(shù)組，重復(fù)上述步驟，遞歸地構(gòu)建左右子樹(shù)。

• 返回根節(jié)點(diǎn)：遞歸結(jié)束時(shí)，返回構(gòu)建的樹(shù)的根節(jié)點(diǎn)。

下面是具體的算法邏輯：

• 定義一個(gè)遞歸函數(shù)sortedArrayToBST，它接收有序數(shù)組的起始索引和結(jié)束索引作為參數(shù)。
• 計(jì)算中間索引mid：mid = (start+ end) / 2。
• 使用mid索引處的值創(chuàng)建一個(gè)新的樹(shù)節(jié)點(diǎn)。
• 遞歸地調(diào)用sortedArrayToBST來(lái)構(gòu)建左子樹(shù)，使用start和mid - 1作為新的參數(shù)。
• 遞歸地調(diào)用sortedArrayToBST來(lái)構(gòu)建右子樹(shù)，使用mid + 1和end作為新的參數(shù)。
• 將左子樹(shù)和右子樹(shù)分別賦值給新創(chuàng)建的根節(jié)點(diǎn)的左右子節(jié)點(diǎn)。
• 返回根節(jié)點(diǎn)。

2. 復(fù)雜度：時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(logn)。

3. c++ demo：

#include <iostream>
#include <vector>// 定義二叉樹(shù)節(jié)點(diǎn)
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};// 將有序數(shù)組轉(zhuǎn)換為二叉搜索樹(shù)的函數(shù)
class Solution {
public:TreeNode* sortedArrayToBST(std::vector<int>& nums) {return sortedArrayToBSTHelper(nums, 0, nums.size() - 1);}private:TreeNode* sortedArrayToBSTHelper(std::vector<int>& nums, int start, int end) {if (start > end) {return nullptr;}// 選擇中間的元素作為根節(jié)點(diǎn)int mid = start + (end - start) / 2;TreeNode* node = new TreeNode(nums[mid]);// 遞歸地構(gòu)建左子樹(shù)和右子樹(shù)node->left = sortedArrayToBSTHelper(nums, start, mid - 1);node->right = sortedArrayToBSTHelper(nums, mid + 1, end);return node;}
};// 輔助函數(shù)：中序遍歷二叉樹(shù)并打印節(jié)點(diǎn)值
void inorderTraversal(TreeNode* node) {if (!node) return;inorderTraversal(node->left);std::cout << node->val << " ";inorderTraversal(node->right);
}// 輔助函數(shù)：釋放二叉樹(shù)內(nèi)存
void deleteTree(TreeNode* node) {if (!node) return;deleteTree(node->left);deleteTree(node->right);delete node;
}int main() {// 創(chuàng)建Solution實(shí)例Solution solution;// 有序數(shù)組std::vector<int> nums = { -10, -3, 0, 5, 9 };// 將有序數(shù)組轉(zhuǎn)換為BSTTreeNode* root = solution.sortedArrayToBST(nums);// 中序遍歷BST并打印節(jié)點(diǎn)值std::cout << "Inorder traversal of the constructed BST:" << std::endl;inorderTraversal(root);std::cout << std::endl;// 釋放二叉樹(shù)內(nèi)存deleteTree(root);return 0;
}

• 輸出結(jié)果：

Inorder traversal of the constructed BST:
-10 -3 0 5 9

4. demo 倉(cāng)庫(kù)地址：sortedArrayToBST