English
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.
Solution:
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
}
...