## Leetcode: convert ordered array to binary search tree (Python)

A good function 2020-11-13 02:53:41
leetcode convert ordered array binary

## 1. Title Description

An ordered array in ascending order , Convert to a highly balanced binary search tree .

In this question , A highly balanced binary tree refers to each node of a binary tree The absolute value of the height difference between the left and right subtrees is not more than 1.

Example :

Given an ordered array : [-10,-3,0,5,9],

One possible answer is ：[0,-3,9,-10,null,5], It can represent the following highly balanced binary search tree ：

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

## 2. Ideas

Because arrays are ordered , So the root node of the binary search tree is the midpoint of the array . And then recurs to the left and right arrays , Get the left and right subtrees .

### 2.1 python Code

``````class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
if not nums: return
mid = len(nums) // 2
root = TreeNode(nums[mid])
root.left = self.sortedArrayToBST(nums[:mid])
root.right = self.sortedArrayToBST(nums[mid+1:])
return root
``````