108. Convert Sorted Array to Binary Search Tree
給定一個按升序排列的整數數組 nums，將其轉換為高度平衡的二元搜索樹（BST）。
範例：
輸入：nums = [-10,-3,0,5,9] 輸出：[0,-3,9,-10,null,5] 解釋：[0,-10,5,null,-3,null,9] 也是被接受的輸出。
這表明根據給定的有序數組，可以構造出多種高度平衡的二元搜索樹。這些樹的結構可能不同，但它們都是有效的高度平衡BST。
Python
from typing import List, Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
if not nums:
return None
# Helper function to convert array to BST
def convertToBST(left, right):
if left > right:
return None
# Always choose the middle element to ensure balance
mid = (left + right) // 2
node = TreeNode(nums[mid])
node.left = convertToBST(left, mid - 1)
node.right = convertToBST(mid + 1, right)
return node
return convertToBST(0, len(nums) - 1)
17.69MB, 69ms
C++
class Solution {
private:
TreeNode* buildBST(vector<int>& nums, int left, int right) {
if (left > right) {
return nullptr;
}
int mid = left + (right - left) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = buildBST(nums, left, mid - 1);
root->right = buildBST(nums, mid + 1, right);
return root;
}
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return buildBST(nums, 0, nums.size() - 1);
}
};
20.78MB, 20ms
Javascript
/**
* 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) {
// Helper function to build the BST
function buildBST(left, right) {
if (left > right) {
return null;
}
// Find the middle element
const mid = Math.floor((left + right) / 2);
// Create a new node with the middle element
const root = new TreeNode(nums[mid]);
// Recursively build left and right subtrees
root.left = buildBST(left, mid - 1);
root.right = buildBST(mid + 1, right);
return root;
}
// Start the recursive process with the entire array
return buildBST(0, nums.length - 1);
};
53.02MB, 59ms
