﻿ 【leetcode】108. Convert Sorted Array to Binary Search Tree

### 【leetcode】108. Convert Sorted Array to Binary Search Tree

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```

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

class Solution(object):
def recursive(self,node,nums):
mid = len(nums)/2
left_num = nums[:mid]
if len(left_num) > 0:
node.left = TreeNode(left_num[len(left_num)/2])
self.recursive(node.left,left_num)
right_num = nums[mid+1:]
if len(right_num) > 0:
node.right = TreeNode(right_num[len(right_num)/2])
self.recursive(node.right,right_num)

def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
if len(nums) == 0:
return None
root = TreeNode(nums[len(nums)/2])
self.recursive(root,nums)
return root```