convert_sorted_array_to_binary_search_tree
1from utils import TreeNode, to_bst 2from typing import Optional 3# @leet start 4class Solution: 5 def sortedArrayToBST(self, nums: list[int]) -> Optional[TreeNode]: 6 """ 7 To turn a sorted list into a BST, we can look at the properties of a sorted list and a BST. 8 To build a BST, we want the following properties: 9 The current node's val should be node.left.val < node.val < node.right.val 10 Since the list is sorted, the middle value perfectly splits the tree in two. 11 So, the root node's value is the middle value. 12 Then, we recurse onto the right hand side by defining its value as between the midpoint and the end. 13 Likewise, the left hand side is between the start and the midpoint. 14 """ 15 if not nums: 16 return None 17 mid = len(nums) // 2 18 root = TreeNode(nums[mid]) 19 root.left = self.sortedArrayToBST(nums[:mid]) 20 root.right = self.sortedArrayToBST(nums[mid+1:]) 21 return root 22 23# @leet end 24sol = Solution() 25def test(): 26 assert(sol.sortedArrayToBST([-10, -3, 0, 5, 9]) == to_bst([-10, -3, 0, 5, 9])) 27 assert(sol.sortedArrayToBST([]) == to_bst([])) 28 assert(sol.sortedArrayToBST([1, 3]) == to_bst([1, 3]))
class
Solution:
5class Solution: 6 def sortedArrayToBST(self, nums: list[int]) -> Optional[TreeNode]: 7 """ 8 To turn a sorted list into a BST, we can look at the properties of a sorted list and a BST. 9 To build a BST, we want the following properties: 10 The current node's val should be node.left.val < node.val < node.right.val 11 Since the list is sorted, the middle value perfectly splits the tree in two. 12 So, the root node's value is the middle value. 13 Then, we recurse onto the right hand side by defining its value as between the midpoint and the end. 14 Likewise, the left hand side is between the start and the midpoint. 15 """ 16 if not nums: 17 return None 18 mid = len(nums) // 2 19 root = TreeNode(nums[mid]) 20 root.left = self.sortedArrayToBST(nums[:mid]) 21 root.right = self.sortedArrayToBST(nums[mid+1:]) 22 return root
6 def sortedArrayToBST(self, nums: list[int]) -> Optional[TreeNode]: 7 """ 8 To turn a sorted list into a BST, we can look at the properties of a sorted list and a BST. 9 To build a BST, we want the following properties: 10 The current node's val should be node.left.val < node.val < node.right.val 11 Since the list is sorted, the middle value perfectly splits the tree in two. 12 So, the root node's value is the middle value. 13 Then, we recurse onto the right hand side by defining its value as between the midpoint and the end. 14 Likewise, the left hand side is between the start and the midpoint. 15 """ 16 if not nums: 17 return None 18 mid = len(nums) // 2 19 root = TreeNode(nums[mid]) 20 root.left = self.sortedArrayToBST(nums[:mid]) 21 root.right = self.sortedArrayToBST(nums[mid+1:]) 22 return root
To turn a sorted list into a BST, we can look at the properties of a sorted list and a BST. To build a BST, we want the following properties: The current node's val should be node.left.val < node.val < node.right.val Since the list is sorted, the middle value perfectly splits the tree in two. So, the root node's value is the middle value. Then, we recurse onto the right hand side by defining its value as between the midpoint and the end. Likewise, the left hand side is between the start and the midpoint.
sol =
<Solution object>
def
test():