109. Convert Sorted List to Bina

题目

将一个升序排列的数组转换为一刻平衡的二叉搜索树

解析

二叉搜索树是左子树小于根节点，又子树大于根节点，那么对于一个单调递增数组来说，我们任意选择一个数，这个数组左侧是小于该节点的，右侧是大于该节点的。恰好符合二叉搜索树的结构，然后我们递归下去，即可得到一颗完整的二叉搜索树，为了保证高度平衡，选择中间节点，保证左右子树结构相同，节点相同，那么高度自然也相同。

区别在于，这个题目给出了链表，比起直接数组切片访问，复杂了一些，将其转为数组。

伪代码

代码

func sortedListToBST(head *ListNode) *TreeNode {
    nums := make([]int, 0)
    for head != nil {
        nums=append(nums, head.Val)
        head=head.Next
    }
    return tobst(nums)
}

func tobst(nums []int) *TreeNode {
    if len(nums) == 0 {
        return nil
    }
    k := len(nums) / 2
    node := &TreeNode{Val: nums[k]}
    node.Left = tobst(nums[:k])
    node.Right = tobst(nums[k+1:])
    return node
}

image.png