108.md

108. Convert Sorted Array to Binary Search Tree

Description

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function(nums) {
    "use strict";
    if (nums.length === 0) {
        return [];
    }
    function constructBST(left, right) {
        let mid = Math.floor((left+right)/2);
        let node = new TreeNode(nums[mid]);
        if (left !== mid) {
            node.left = constructBST(left, mid-1);
        }
        if (right !== mid) {
            node.right = constructBST(mid+1, right);
        }
        return node;
    }
    return constructBST(0, nums.length-1);
};