-
Notifications
You must be signed in to change notification settings - Fork 0
LC 0095 [M] Unique Binary Search Trees II
Code with Senpai edited this page Jan 27, 2022
·
18 revisions
this is just postorder + double nested for loop template that you need to memorize to generate combinations of BSTs
# 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 generateTrees(self, n: int) -> List[Optional[TreeNode]]:
def dfs(nums):
if not nums:
return [None]
ans = []
for i in range(len(nums)):
leftTrees = dfs(nums[:i]) # prefix
rightTrees = dfs(nums[i+1:]) # suffix
for l in leftTrees:
for r in rightTrees:
root = TreeNode(nums[i])
root.left = l
root.right = r
ans.append(root)
return ans
nums = range(1, n + 1)
return dfs(nums)
# 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 generateTrees(self, n: int) -> List[TreeNode]:
def dfs(start, end):
if start > end:
return [None]
res = []
for i in range(start, end + 1):
left_subtrees = dfs(start, i - 1) # (i - 1) - 0 + 1
right_subtrees = dfs(i + 1, end) # (n) - i + 1
for left_subtree in left_subtrees:
for right_subtree in right_subtrees:
root = TreeNode(i)
root.left = left_subtree
root.right = right_subtree
res.append(root)
return res
return dfs(1, n) if n else []
footer