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

### 题目地址(108. 将有序数组转换为二叉搜索树)

<https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/>

### 题目描述

```
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

```

### 前置知识

* [二叉搜索树](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/thinkings/basic-data-structure)
* [平衡二叉树](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/thinkings/basic-data-structure)
* [递归](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/thinkings/dynamic-programming)

### 公司

* 阿里
* 腾讯
* 百度
* 字节
* airbnb

### 思路

由于输入是一个**升序排列的有序数组**。因此任意选择一点，将其作为根节点，其左部分左节点，其右部分右节点即可。 因此我们很容易写出递归代码。

而题目要求是**高度平衡**的二叉搜索树，因此我们必须要取中点。 不难证明：`由于是中点，因此左右两部分差不会大于 1，也就是说其形成的左右子树节点数最多相差 1，因此左右子树高度差的绝对值不超过 1`。

形象一点来看就像你提起一根绳子，从中点提的话才能使得两边绳子长度相差最小。

![image.png](https://p.ipic.vip/idi8m0.jpg)

### 关键点

* 找中点

### 代码

代码支持：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<int>& nums) {
        return reBuild(nums, 0, nums.size()-1);
    }

    TreeNode* reBuild(vector<int>& 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 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。

公众号【 [力扣加加](https://p.ipic.vip/h9nm77.jpg)】知乎专栏【 [Lucifer - 知乎](https://www.zhihu.com/people/lu-xiao-13-70)】

点关注，不迷路！