# Python dynamic programming.

• At each node, we try to split a range [start, end] and choose a value as the root. Then the left subtree is assigned the range [start, value - 1] and the right subtree has the range [value + 1, end].
Once a same range [start, end] is encountered again, we just retrieve it by memoization.

``````class Solution(object):
def generateTrees(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
if n < 1:
return []
self.memory = [[[] for _ in range(n + 1)] for _ in range(n + 1)]
return self.buildTrees(1, n)

def buildTrees(self, start, end):
if start > end:
return [None]
if start == end:
return [TreeNode(start)]
if self.memory[start][end]:
return self.memory[start][end]
for val in range(start, end+1):
leftTrees = self.buildTrees(start, val - 1)
rightTrees = self.buildTrees(val+1, end)
for left in leftTrees:
for right in rightTrees: # note: here we may share left and right for various trees
root = TreeNode(val) # but it doesn't affect the results
self.memory[start][end].append(root)
root.left = left
root.right = right
return self.memory[start][end]``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.