LeetCode-108.将有序数组转换为二叉搜索树

二叉树#

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

示例 1：

1
输入：nums = [-10,-3,0,5,9]
2
输出：[0,-3,9,-10,null,5]
3
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

1
输入：nums = [1,3]
2
输出：[3,1]
3
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

递归的解法

1
/**
2
 * Definition for a binary tree node.
3
 * type TreeNode struct {
4
 *     Val int
5
 *     Left *TreeNode
6
 *     Right *TreeNode
7
 * }
8
 */
9
func sortedArrayToBST(nums []int) *TreeNode {
10
    if len(nums) == 0 {
11
        return nil
12
    }
13

14
    mid := len(nums)/2
15

16
    root := &TreeNode{Val: nums[mid]}
17

18
    root.Left = sortedArrayToBST(nums[:mid])
19
    root.Right = sortedArrayToBST(nums[mid+1:])
20

21
    return root
22
}