# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def generateTrees(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
if n == 0:
return []
return self.build(1,n)
def build(self, start, end):
res = []
if start > end:
res.append(None)
return res
else:
for rootIndex in range(start,end+1):
leftList = self.build(start, rootIndex-1)
rightList = self.build(rootIndex+1, end)
for eachLeft in leftList:
for eachRight in rightList:
root = TreeNode(rootIndex)
root.left = eachLeft
root.right = eachRight
res.append(root)
return res
https://leetcode.com/problems/unique-binary-search-trees-ii/#/description
Given an integer n, generate all structurally unique **BST**'s (binary search trees) that store values 1...n.
For example,
Given n = 3, your program should return all 5 unique BST's shown below.
```
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
```