LC #95 - Unique Binary Search Trees II

**Unique Binary Search Trees II**

Description

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1 ... n.

Example

1
2
3
4
5
6
7
8
9
Input: 3
Output:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]

Solution

Unique BST Number(leetcode #96)

This problem is unique BST I, and it’s to find out the number of unique BST. This solution is a little tricky, I looked at the discussion part because I have no thought about it. The solution impressed me a lot, using Dynamic Programming. So how? We traverse every node from 1 to n, and every node should have the chance to be the root node, so when this node is root, how many unique BST do we have ? The answer is (unique BST combined with left) * (unique BST combined with right). BUT there is nothing to do with DP, let us see, (1, 2, 3) has the same number unique BST as (3, 4, 5). So when we try to calculate the right part, we have already know it. The following algorithm will be more straightforward.

Algorithm

Python

1
2
3
4
5
6
7
8
9
def numTrees(self, n):
if not n:
return 1
dp = [0] * (n + 1)
dp[0] = dp[1] = 1 # null counts for 1, dp is the total number of unique BST with 1...i
for i in range(2, n + 1): # end at i
for j in range(1, i + 1): # the current root in 1...i
dp[i] += dp[j - 1] * dp[i - j] # (2, 3 ,4) has the same number as (1, 2, 3)
return dp[n]
Complexity
  • Time Complexity: O(N^2)
  • Space Complexity: O(N)

Unique BST root

Now the current problem is to have all the unique BST, based on the way to calculate number, we can come up with a similar thought, that is we have the current root, then combine all the left with all the right part. This can be done recursively.

Algorithm

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def generateTrees(n):
if not n:
return []
def create(s, e):
if s > e:
return [None]
trees = [] # store all unique BST
for i in range(s, e + 1): # i is the current root
left = create(s, i - 1)
right = create(i + 1, e)
root = TreeNode(i)
for l in left: # a combination of left and right part
for r in right:
root.left, root.right = l, r
trees.append(root)
return create(1, n)
0%