108. Convert Sorted Array to Binary Search Tree

Leetcode

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

題目

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 1:

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

Example 2:

Input: nums = [1,3]
Output: [3,1]
Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.

解答

• 方法一

這題根據子樹排序的方式有多種的解答

方法一的方式為

Choose Left Middle Node as a Root (每次挑選中間值時都選偏左的)

input: [-10, -3, 0, 5, 9]

ans: [0, -10, 5, null, -3, null, 9]

var sortedArrayToBST = function(nums) {
    const getNode = (left, right) => {
        if (left > right) return null;
        
        const mid = Math.floor((left + right) / 2);
        const val = nums[mid];
        const node = new TreeNode(val);
        
        node.left = getNode(left, mid - 1);
        node.right = getNode(mid + 1, right);
        return node;
    }
    
    return getNode(0, nums.length - 1);
};

Runtime: 129 ms, faster than 15.88% of JavaScript online submissions for Convert Sorted Array to Binary Search Tree.

Memory Usage: 44.6 MB, less than 53.40% of JavaScript online submissions for Convert Sorted Array to Binary Search Tree.

• 方法二

Choose Right Middle Node as a Root (每次挑選中間值時都選偏左的)

input: [-10, -3, 0, 5, 9]

ans: [0, -3, 9, -10, null, 5]

var sortedArrayToBST = function(nums) {
    const getNode = (left, right) => {
        if (left > right) return null;
        
        const mid = Math.ceil((left + right) / 2);
        const val = nums[mid];
        const node = new TreeNode(val);
        
        node.left = getNode(left, mid - 1);
        node.right = getNode(mid + 1, right);
        return node;
    }
    
    return getNode(0, nums.length - 1);
};

Runtime: 92 ms, faster than 64.34% of JavaScript online submissions for Convert Sorted Array to Binary Search Tree.

Memory Usage: 44.9 MB, less than 30.59% of JavaScript online submissions for Convert Sorted Array to Binary Search Tree.