-
Notifications
You must be signed in to change notification settings - Fork 5
/
Unique_Binary_Search_Trees_II.py
35 lines (28 loc) · 1.09 KB
/
Unique_Binary_Search_Trees_II.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# 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]]:
if n == 0:
return []
memo = {}
def generate_trees(start, end):
if (start, end) in memo:
return memo[(start, end)]
trees = []
if start > end:
trees.append(None)
return trees
for root_val in range(start, end + 1):
left_trees = generate_trees(start, root_val - 1)
right_trees = generate_trees(root_val + 1, end)
for left_tree in left_trees:
for right_tree in right_trees:
root = TreeNode(root_val, left_tree, right_tree)
trees.append(root)
memo[(start, end)] = trees
return trees
return generate_trees(1, n)