( “树” 之 BST) 108. 将有序数组转换为二叉搜索树 ——【Leetcode每日一题】

Myth丶恋晨 2024-03-23 16:12 85阅读 0赞

### 108. 将有序数组转换为二叉搜索树 ###

给你一个整数数组 `nums` ，其中元素已经按 **升序** 排列，请你将其转换为一棵 **高度平衡** 二叉搜索树。

**高度平衡** 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

**示例 1：**  
![在这里插入图片描述][3f0b70958a194e719b940fdfc827be50.png]

> 输入：nums = \[-10,-3,0,5,9\]  
> 输出：\[0,-3,9,-10,null,5\]  
> 解释：\[0,-10,5,null,-3,null,9\] 也将被视为正确答案：  
> ![在这里插入图片描述][15d4859280ab411e92e4e7a25d38681c.png]

##### 示例 2： #####

![在这里插入图片描述][cf5b1102d57247509ed8d33e2a2ae834.png]

> 输入：nums = \[1,3\]  
> 输出：\[3,1\]  
> 解释：\[1,null,3\] 和 \[3,1\] 都是高度平衡二叉搜索树。

**提示：**

*   1 < = n u m s . l e n g t h < = 1 0 4 1 <= nums.length <= 10^4 1<=nums.length<=104
 *   − 1 0 4 < = n u m s \[ i \] < = 1 0 4 -10^4 <= nums\[i\] <= 10^4 −104<=nums\[i\]<=104
 *  `nums` 按 **严格递增** 顺序排列

#### 思路：递归 ####

我们可以构造一个二叉搜索树（BST）：根节点大于等于左子树所有节点，小于等于右子树所有节点。

所以我们让根节点等于该数组的中位数，该中位数左边就是左子树，右边就是右子树，分别在递归处理左右子树，既可得到高度平衡二叉树。

*  这里我们要传入需要处理的数组的区间。
 *  返回该相对区间的中位数生成的节点。

#### 代码：(Java、C++) ####

**Java**

class Solution {
        
        public TreeNode sortedArrayToBST(int[] nums) {
        
            TreeNode root = toBST(nums, 0, nums.length - 1);
            return root;
        }
        public TreeNode toBST(int[] nums, int be, int ed){
        
            if(be > ed) return null;
            TreeNode root = new TreeNode(nums[be + (ed - be) / 2]);
            root.left = toBST(nums, be, be + (ed - be) / 2 - 1);
            root.right = toBST(nums, be + (ed - be) / 2 + 1, ed);
            return root;
        }
    }

**C++**

class Solution {
        
    public:
        TreeNode* sortedArrayToBST(vector<int>& nums) {
        
            TreeNode* root = toBST(nums, 0, nums.size() - 1);
            return root;
        }
        TreeNode* toBST(vector<int>& nums, int be, int ed){
        
            if(be > ed) return nullptr;
            TreeNode* root = new TreeNode(nums[be + (ed - be) / 2]);
            root->left = toBST(nums, be, be + (ed - be) / 2 - 1);
            root->right = toBST(nums, be + (ed - be) / 2 + 1, ed);
            return root;
        }
    };

##### 运行结果： #####

![在这里插入图片描述][f3bfc251797743e89c970f41b0c8b8ae.png]

##### 复杂度分析： #####

*  **时间复杂度**： O ( n ) O(n) O(n)，其中 `n` 是数组的长度。每个数字只访问一次。
 *  **空间复杂度**： O ( l o g ⁡ n ) O(log⁡n) O(log⁡n)，其中`n` 是数组的长度。空间复杂度不考虑返回值，因此空间复杂度主要取决于递归栈的深度，递归栈的深度是  O ( l o g ⁡ n ) O(log⁡n) O(log⁡n)。

题目来源：[力扣。][Link 1]

> 放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！  
> 关注我 [leetCode专栏][leetCode]，每日更新！

##### 注： 如有不足，欢迎指正！ #####

[3f0b70958a194e719b940fdfc827be50.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/de6225a4dbaf462683934644769b3815.png
[15d4859280ab411e92e4e7a25d38681c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/812bc1b66c1b46d9a23fec5db53f21eb.png
[cf5b1102d57247509ed8d33e2a2ae834.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/bf7b7cdd764d4ffabb203057f22d3166.png
[f3bfc251797743e89c970f41b0c8b8ae.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/d6692ca0d7294907a9bab7081b0a35f6.png
[Link 1]: https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/?orderBy=most_votes%3ForderBy%3Dmost_votes%3ForderBy%3Dmost_votes%3ForderBy%3Dmost_votes
[leetCode]: http://t.csdn.cn/kQLJO