Description:
Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n.
Example:
Solution:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def generateTrees(self, n: int) -> List[TreeNode]:
if n == 0:
return []
result = []
ls = list(range(1,n+1))
def iterate(ls):
if not ls:
return [None]
# if len(ls) == 1:
# return [TreeNode(ls[0])]
# if len(ls) == 2:
# result = [TreeNode(ls[0]),TreeNode(ls[1])]
# result[0].right = TreeNode(ls[1])
# result[1].left = TreeNode(ls[0])
# return result
ret = []
for i in range(len(ls)):
lefts = iterate(ls[:i])
rights = iterate(ls[i+1:])
cache_result = [TreeNode(ls[i]) for t in range(len(lefts)*len(rights))]
for j in range(len(lefts)):
for k in range(len(rights)):
index = j*len(rights)+k
cache_result[index].left = lefts[j]
cache_result[index].right = rights[k]
ret += cache_result
return ret
return iterate(ls)
Runtime: 60 ms, faster than 80.28% of Python3 online submissions for Unique Binary Search Trees II.
Memory Usage: 14.7 MB, less than 84.71% of Python3 online submissions for Unique Binary Search Trees II.
