class Solution:
def generateTrees(self, n: int) -> List[TreeNode]:
def helper(start, end):
if start > end:
return [None, ]
all_trees = []
for i in range(start, end+1):
left_trees = helper(start, i-1)
right_trees = helper(i+1, end)
for l in left_trees:
for r in right_trees:
current_tree = TreeNode(i)
current_tree.left = l
current_tree.right = r
all_trees.append(current_tree)
return all_trees
return helper(1, n) if n else []
Runtime: 52 ms, faster than 87.17% of Python3 online submissions for Unique Binary Search Trees II.
Memory Usage: 14.2 MB, less than 80.00% of Python3 online submissions for Unique Binary Search Trees II.
看不懂的解
class Solution:
def generateTrees(self, n: int) -> List[TreeNode]:
def node(val, left, right):
node = TreeNode(val)
node.left = left
node.right = right
return node
def trees(first, last):
return [node(root, left, right)
for root in range(first, last+1)
for left in trees(first, root-1)
for right in trees(root+1, last)]or[None]
return trees(1, n) if n != 0 else []
Runtime: 60 ms, faster than 56.45% of Python3 online submissions for Unique Binary Search Trees II.
Memory Usage: 14.8 MB, less than 73.33% of Python3 online submissions for Unique Binary Search Trees II.
动态规划
class Solution:
def generateTrees(self, n: int) -> List[TreeNode]:
if n == 0:
return []
tree_list = [[[None]] * (n+2) for i in range(n+2)]
for i in range(1, n+1):
tree_list[i][i] = [TreeNode(i)]
for j in range(i-1, 0, -1):
tree_list[j][i] = []
for k in range(j, i+1):
for left in tree_list[j][k-1]:
for right in tree_list[k+1][i]:
root = TreeNode(k)
root.left, root.right = left, right
tree_list[j][i].append(root)
return tree_list[1][n]
Runtime: 44 ms, faster than 98.40% of Python3 online submissions for Unique Binary Search Trees II.
Memory Usage: 13.4 MB, less than 100.00% of Python3 online submissions for Unique Binary Search Trees II.