 # Tree - 108. Convert Sorted Array to Binary Search Tree Easy

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

go：

``````/**

* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func sortedArrayToBST(nums []int) *TreeNode {
if nums == nil || len(nums) == 0 {
return nil
}

return recursion(nums, 0, len(nums))
}

func recursion(nums []int, low int, high int) *TreeNode {
if low >= high { // leaf
return nil
}

mid := (high-low)/2 + low

return &TreeNode{
Val:   nums[mid],
Left:  recursion(nums, low, mid),
Right: recursion(nums, mid+1, high)}
}
``````

Nothing just happens, it's all part of a plan.