109. Convert Sorted List to Binary Search Tree
範例：
輸入：head = [-10,-3,0,5,9] 輸出：[0,-3,9,-10,null,5] 解釋：一個可能的答案是 [0,-3,9,-10,null,5]，它表示所示的高度平衡二元搜索樹。
Python
from typing import Optional
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 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 sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
# Convert linked list to array
nums = []
while head:
nums.append(head.val)
head = head.next
# Helper function to convert array to BST
def convertToBST(left, right):
if left > right:
return None
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)
21.18MB, 96ms
C++
class Solution {
private:
TreeNode* sortedListToBSTHelper(ListNode*& head, int start, int end) {
if (start > end) {
return nullptr;
}
int mid = start + (end - start) / 2;
// Recursively construct the left subtree
TreeNode* left = sortedListToBSTHelper(head, start, mid - 1);
// Create the root node
TreeNode* root = new TreeNode(head->val);
root->left = left;
// Move head to the next node
head = head->next;
// Recursively construct the right subtree
root->right = sortedListToBSTHelper(head, mid + 1, end);
return root;
}
int getLength(ListNode* head) {
int length = 0;
while (head) {
length++;
head = head->next;
}
return length;
}
public:
TreeNode* sortedListToBST(ListNode* head) {
int length = getLength(head);
return sortedListToBSTHelper(head, 0, length - 1);
}
};
27.57MB, 19ms
Javascript
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* 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 {ListNode} head
* @return {TreeNode}
*/
var sortedListToBST = function(head) {
// Helper function to get the length of the linked list
const getLength = (node) => {
let length = 0;
while (node) {
length++;
node = node.next;
}
return length;
};
// Helper function to build the BST
const buildBST = (start, end) => {
if (start > end) {
return null;
}
const mid = Math.floor((start + end) / 2);
// Build left subtree
const left = buildBST(start, mid - 1);
// Create root node
const root = new TreeNode(head.val);
root.left = left;
// Move head to next node
head = head.next;
// Build right subtree
root.right = buildBST(mid + 1, end);
return root;
};
const length = getLength(head);
return buildBST(0, length - 1);
};
55.62MB, 75ms
