6/23/2017 - 8:46 AM

## 95. Unique Binary Search Trees II

1. Unique Binary Search Trees II
``````# 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
`````````