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

leetcode
61

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

思路：

将有序数组变成bst，做法就是取出数组中的中位数当root节点，然后将root节点两边分别递归求bst，注意这里的中位数，如果是偶数个数组是向上取整，即[0, 1, 7, 8]的root是7,下标为2。

代码：

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)}
}