# 0108. 将有序数组转换为二叉搜索树
### 题目地址(108. 将有序数组转换为二叉搜索树)
### 题目描述
```
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
```
### 前置知识
* [二叉搜索树](/leetcode-solution/thinkings/basic-data-structure.md)
* [平衡二叉树](/leetcode-solution/thinkings/basic-data-structure.md)
* [递归](/leetcode-solution/thinkings/dynamic-programming.md)
### 公司
* 阿里
* 腾讯
* 百度
* 字节
* airbnb
### 思路
由于输入是一个**升序排列的有序数组**。因此任意选择一点，将其作为根节点，其左部分左节点，其右部分右节点即可。 因此我们很容易写出递归代码。
而题目要求是**高度平衡**的二叉搜索树，因此我们必须要取中点。 不难证明：`由于是中点，因此左右两部分差不会大于 1，也就是说其形成的左右子树节点数最多相差 1，因此左右子树高度差的绝对值不超过 1`。
形象一点来看就像你提起一根绳子，从中点提的话才能使得两边绳子长度相差最小。
### 关键点
* 找中点
### 代码
代码支持：JS，C++，Java，Python
JS Code:
```js
var sortedArrayToBST = function (nums) {
// 由于数组是排序好的，因此一个思路就是将数组分成两半，一半是左子树，另一半是右子树
// 然后运用“树的递归性质”递归完成操作即可。
if (nums.length === 0) return null;
const mid = nums.length >> 1;
const root = new TreeNode(nums[mid]);
root.left = sortedArrayToBST(nums.slice(0, mid));
root.right = sortedArrayToBST(nums.slice(mid + 1));
return root;
};
```
Python Code:
```py
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
if not nums: return None
mid = (len(nums) - 1) // 2
root = TreeNode(nums[mid])
root.left = self.sortedArrayToBST(nums[:mid])
root.right = self.sortedArrayToBST(nums[mid + 1:])
return root
```
**复杂度分析**
* 时间复杂度：$O(N)$
* 空间复杂度：每次递归都 copy 了 N 的 空间，因此空间复杂度为 $O(N ^ 2)$
然而，实际上没必要开辟新的空间：
C++ Code:
```
class Solution {
public:
TreeNode* sortedArrayToBST(vector& nums) {
return reBuild(nums, 0, nums.size()-1);
}
TreeNode* reBuild(vector& nums, int left, int right)
{
// 终止条件：中序遍历为空
if(left > right)
{
return NULL;
}
// 建立当前子树的根节点
int mid = (left+right)/2;
TreeNode * root = new TreeNode(nums[mid]);
// 左子树的下层递归
root->left = reBuild(nums, left, mid-1);
// 右子树的下层递归
root->right = reBuild(nums, mid+1, right);
// 返回根节点
return root;
}
};
```
Java Code:
```java
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return dfs(nums, 0, nums.length - 1);
}
private TreeNode dfs(int[] nums, int lo, int hi) {
if (lo > hi) {
return null;
}
int mid = lo + (hi - lo) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = dfs(nums, lo, mid - 1);
root.right = dfs(nums, mid + 1, hi);
return root;
}
}
```
Python Code:
```python
class Solution(object):
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
return self.reBuild(nums, 0, len(nums)-1)
def reBuild(self, nums, left, right):
# 终止条件：
if left > right:
return
# 建立当前子树的根节点
mid = (left + right)//2
root = TreeNode(nums[mid])
# 左右子树的下层递归
root.left = self.reBuild(nums, left, mid-1)
root.right = self.reBuild(nums, mid+1, right)
return root
```
**复杂度分析**
* 时间复杂度：$O(N)$
* 空间复杂度：由于是平衡二叉树，因此隐式调用栈的开销为 $O(logN)$
更多题解可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。
公众号【 [力扣加加](https://p.ipic.vip/h9nm77.jpg)】知乎专栏【 [Lucifer - 知乎](https://www.zhihu.com/people/lu-xiao-13-70)】
点关注，不迷路！
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/easy/108.convert-sorted-array-to-binary-search-tree.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.