2021-10-07：将有序数组转换为二叉搜索树。给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵

福大大架构师每日一题

发布于 2021-10-14 11:12:42

4700

发布于 2021-10-14 11:12:42

2021-10-07：将有序数组转换为二叉搜索树。给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵高度平衡二叉搜索树。高度平衡二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。力扣108。

福大大答案2021-10-07：

自然智慧即可。找中点，左节点=左边递归，右节点=右边递归。

时间复杂度：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
}

执行结果如下：