定义

左孩子的值全部小于根节点，右孩子的值全部大于跟结点，左孩子、右孩子同样满足上述条件。

假如有3个结点，总共有5个可能的BST:
1
2
3
4
5
1         3     3      2      1
  \        /     /       /  \       \
   3    2    1      1    3      2
  /     /        \                     \
 2     1         2                   3
问题一：给定结点的个数，计算BST的个数

分析

1
2
3
4
5
6
令f(0) = 1
f(1) = f(0)*f(0)
f(2) = f(1)*f(0) + f(0)*f(1)
f(3) = f(2)*f(0) + f(1)*f(1) + f(0)*f(2)
……
f(n) = f(n-1)*f(0) + f(n-2)*f(1) +……f(0)*f(n-1)
问题二：给定结点的个数，求出所有的BST

分析

递归实现，保存左孩子所有的组合、右孩子所有的组合，之后按着求个数的模式组合左右孩子。