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

[Geekhyt]

原题链接

递归

1. 二叉搜索树的中序遍历是升序的，本题中给出的数组刚好是升序的，相当于通过中序遍历恢复二叉搜索树
2. 可以选择升序序列中的任意位置的元素作为根节点，该元素左边的升序序列构建左子树，右边的升序序列构建右子树
3. 题目又要求高度平衡，所以我们需要选择升序序列的中间位置的元素作为根节点即可

const sortedArrayToBST = function (nums) {
    const buildTree = (Arr, left, right) => {
        if (left > right) return null

        let mid = Math.floor(left + (right - left) / 2)

        let root = new TreeNode(Arr[mid])
        root.left = buildTree(Arr, left, mid - 1)
        root.right = buildTree(Arr, mid + 1, right)
        return root
    }
    return buildTree(nums, 0, nums.length - 1)
}

• 时间复杂度：O(n)
• 空间复杂度：O(logn)