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

題目

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

示例 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 <= 10⁴
• -10⁴ <= nums[i] <= 10⁴
• nums 按 嚴(yán)格遞增 順序排列

平衡二叉搜索樹

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

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

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

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

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

題解

遞歸法

1. 解題思路：

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

以下是解題步驟：

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

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

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

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

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

下面是具體的算法邏輯：

• 定義一個(gè)遞歸函數(shù)sortedArrayToBST，它接收有序數(shù)組的起始索引和結(jié)束索引作為參數(shù)。
• 計(jì)算中間索引mid：mid = (start+ end) / 2。
• 使用mid索引處的值創(chuàng)建一個(gè)新的樹節(jié)點(diǎn)。
• 遞歸地調(diào)用sortedArrayToBST來構(gòu)建左子樹，使用start和mid - 1作為新的參數(shù)。
• 遞歸地調(diào)用sortedArrayToBST來構(gòu)建右子樹，使用mid + 1和end作為新的參數(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>// 定義二叉樹節(jié)點(diǎn)
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};// 將有序數(shù)組轉(zhuǎn)換為二叉搜索樹的函數(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)建左子樹和右子樹node->left = sortedArrayToBSTHelper(nums, start, mid - 1);node->right = sortedArrayToBSTHelper(nums, mid + 1, end);return node;}
};// 輔助函數(shù)：中序遍歷二叉樹并打印節(jié)點(diǎn)值
void inorderTraversal(TreeNode* node) {if (!node) return;inorderTraversal(node->left);std::cout << node->val << " ";inorderTraversal(node->right);
}// 輔助函數(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;// 釋放二叉樹內(nèi)存deleteTree(root);return 0;
}

• 輸出結(jié)果：

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

4. demo 倉庫地址：sortedArrayToBST