## 题目描述

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

``````Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

0
/ \
-3   9
/   /
-10  5``````

## 解法一

### 思路

``````     4
/   \
2     6
/ \   / \
1   3 5   7``````

### Python

``````# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
def to_bst(nums, start, end):
if start > end:
return None
mid = (start + end) // 2
node = TreeNode(nums[mid])
node.left = to_bst(nums, start, mid - 1)
node.right = to_bst(nums, mid + 1, end)
return node

return to_bst(nums, 0, len(nums) - 1)``````

### Java

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
class Utils {
TreeNode toBST(int[] nums, int start, int end) {
if (start > end) {
return null;
}
int mid = (start + end) / 2;
TreeNode node = new TreeNode(nums[mid]);
node.left = toBST(nums, start, mid - 1);
node.right = toBST(nums, mid + 1, end);
return node;
}
}
Utils utils = new Utils();
return utils.toBST(nums, 0, nums.length - 1);
}
}``````

### C++

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode *sortedArrayToBST(vector<int> &nums) {
class Utils {
public:
TreeNode *toBST(vector<int> &nums, int start, int end) {
if (start > end) {
return nullptr;
}
int mid = (start + end) / 2;
TreeNode *node = new TreeNode(nums[mid]);
node->left = toBST(nums, start, mid - 1);
node->right = toBST(nums, mid + 1, end);
return node;
}
};
Utils utils;
return utils.toBST(nums, 0, nums.size() - 1);
}
};``````