将有序数组转换为二叉搜索树。给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。力扣108。
自然智慧即可。找中点,左节点=左边递归,右节点=右边递归。
时间复杂度:O(N)。
空间复杂度:O(N)。
代码用golang编写。代码如下:
package main
import "fmt"
func main() {
ret := sortedArrayToBST([]int{1, 2, 3, 4, 5})
fmt.Println(ret)
}
type TreeNode struct {
val int
left *TreeNode
right *TreeNode
}
func sortedArrayToBST(nums []int) *TreeNode {
return process(nums, 0, len(nums)-1)
}
func process(nums []int, L int, R int) *TreeNode {
if L > R {
return nil
}
if L == R {
return &TreeNode{val: nums[L]}
}
M := (L + R) / 2
head := &TreeNode{val: nums[M]}
head.left = process(nums, L, M-1)
head.right = process(nums, M+1, R)
return head
}
执行结果如下: