108 - Convert Sorted Array to Binary Search Tree

108. Convert Sorted Array to Binary Search Tree

Problem Statement

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

 

Example 1:

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

Example 2:

Input: nums = [1,3]
Output: [3,1]
Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.

 

Constraints:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums is sorted in a strictly increasing order.

Solutions

Go

package main

// Definition for a binary tree node.
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func sortedArrayToBST(nums []int) *TreeNode {
	if len(nums) == 0 {
		return nil
	}

	return contructBST(nums, 0, len(nums)-1)
}

func contructBST(nums []int, left, right int) *TreeNode {
	if left > right {
		return nil
	}

	mid := (left + right) / 2
	node := &TreeNode{Val: nums[mid]}
	node.Left = contructBST(nums, left, mid-1)
	node.Right = contructBST(nums, mid+1, right)
	return node
}

...