Problem: Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?

For example,
Given n = 3, there are a total of 5 unique BST’s.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Solution: Unique Binary Search Trees, Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#!/usr/bin/env python
# -*- encoding: utf-8 -*-
# @Date : 2015-01-26 22:29:34
# @Author : NSSimacer
# @Version : 1.0
class Solution:
# @return an integer
def numTrees(self, n):
if n == 0 or n == 1:
return 1
lst = [0] * (n + 1)
lst[0] = 1
lst[1] = 1
lst[2] = 2
if n < 3:
return lst[n]
for i in xrange(3, n + 1):
for j in xrange(0, i):
lst[i] += lst[j] * lst[i - 1 - j]
return lst[n]

节点数为0时,树的个数为1;节点个数为1时,树的个数为1;节点个数为2时,树的个数为2 … 并且,分别画出以0, 1, 2, 3为根的树,可以发现,以N为根的树的个数为左子树的个数乘以右子树的个数。

其实,给定N个节点,能产生的唯一BST数为卡特兰数的第N项:
Catalan number