Open
Description
递归
- 二叉搜索树的中序遍历是升序的,本题中给出的数组刚好是升序的,相当于通过中序遍历恢复二叉搜索树
- 可以选择升序序列中的任意位置的元素作为根节点,该元素左边的升序序列构建左子树,右边的升序序列构建右子树
- 题目又要求高度平衡,所以我们需要选择升序序列的中间位置的元素作为根节点即可
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)