Solution to LeetCode 108 Convert Sorted Array to Binary Search Tree.
LeetCode 108
Convert Sorted Array to Binary Search Tree (Easy). [link]
If [l, r] is left inclusive and right inclusive.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
def buildBST(l,r):
if l > r: return None
m = l + (r - l) //2
root = TreeNode(nums[m])
root.left = buildBST(l, m-1)
root.right = buildBST(m+1, r)
return root
return buildBST(0, len(nums)-1)
If [l, r) is left inclusive and right exclusive.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
def buildBST(l, r):
if l >= r:
return None
m = l + (r - l) //2
root = TreeNode(nums[m])
root.left = buildBST(l, m)
root.right = buildBST(m+1, r)
return root
return buildBST(0, len(nums))
Template of Creating a BST
Recall the property of BST: Vals(root.left) <= root.val <= Vals(root.right). and the property of height balanced BST: Node(root.left) - Node(root.right) <= 1.
The time complexity is O(n), since all nodes need to be added to a BST. The space complexity is O(log n), because the depth of recursion is log n.
def build(arr, l, r):
if l > r: return none
m = l + (r - l) // 2
root = TreeNode(arr[m])
root.left = build(arr, l, m-1)
root.right = build(arr, m+1, r)
return root
