Leetcode 108 - Convert sorted array to bst

Note:

  • As long as you pick the middle as root, you WILL get a balanced BST.
  • Use floor function, so index won’t overflow.

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Example

img

1
2
Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {number[]} nums
* @return {TreeNode}
*/
var sortedArrayToBST = function(nums) {
if (nums.length === 0) return null;
const index = Math.floor((nums.length - 1) / 2);
const node = new TreeNode(nums[index]);
node.left = sortedArrayToBST(nums.slice(0, index));
node.right = sortedArrayToBST(nums.slice(index + 1));
return node;
};