LC 0108 [E] Convert Sorted Array to Binary Search Tree - ALawliet/algorithms GitHub Wiki
- - - - -
(L) M (R)
https://www.youtube.com/watch?v=0K0uCMYq5ng&ab_channel=NeetCode
# 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]:
def binarysplit(l, r):
if l > r: # not l <= r (recursion base case opposite of binary search while l <= r)
return None
m = (l + r) // 2
root = TreeNode(nums[m])
root.left = binarysplit(l, m - 1)
root.right = binarysplit(m + 1, r)
return root
return binarysplit(0, len(nums) - 1)
overly complicated Omkar solution
# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
def helper(P, startP, endP, I, startI, endI):
if startP > endP: return None
rootnode = TreeNode(P[startP])
rootindex = hashmap[P[startP]]
numleft = rootindex - startI
numright = endI - rootindex
rootnode.left = helper(P, startP + 1, startP + numleft, I, startI, rootindex - 1)
rootnode.right = helper(P, startP + numleft +1, endP, I, rootindex + 1, endI)
return rootnode
inorder_value_to_index = {}
for i in range(len(inorder)):
inorder_value_to_index[inorder[i]] = i
return helper(preorder, 0, len(preorder) - 1, inorder, 0, len(inorder) - 1)
'''
top-down tree construction
rootnode
startP numleft numright endP
Preorder: x [Preorder(L)] [Preorder(R)]
Inorder: [Inorder(L)] x [Inorder(R)]
startI numleft rootindex numright endI
if we lookup x in Inorder, we can find Inorder numleft and numright
and since Preorder(L) has same length as Inorder(L), if we now Inorder numleft and numright then we also know Preorder numleft and numright
'''