【二叉查找树】01不同的二叉查找树的个数【Unique Binary Search Trees】

当数组为1，2，3，4，...，n时，基于以下原则构建的BST树具有唯一性：

以i为根节点的树，其左子树由[1，i-1]构成，其右子树由[i+1, n]构成。

我们假定f(i)为以[1，i]能产生的Unique Binary Search Tree的数目，则

如果数组为空，毫无疑问，只有一种BST，即空树，f(0)=1。
如果数组仅有一个元素1，只有一种BST，单个节点，f(1)=1。
如果数组有两个元素1，2，那么有如下两种可能：

1 2

2 1

那么分析可得

f(2) = f(0) * f(1)，1为根的情况

+ f(1) * f(0)，2为根的情况

再看一看3个元素的数组，可以发现BST的取值方式如下：

f(3) = f(0) * f(2)，1为根的情况

+ f(1) * f(1)，2为根的情况

+ f(2) * f(0)，3为根的情况

所以，由此观察，可以得出f的递推公式为：

f(i) = f(k - 1) * f(i - k) ps. k = 1 ... i

由此问题划归为一维动态规划。

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

给定一个n，问有多少个不同的二叉查找树，使得每个节点的值为 1...n?

例如，

给定n=3，这里一共有5中不同的二叉查找树。

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

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

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

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

test.cpp：

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

#include <iostream>
#include <vector>

using namespace std;

int numTrees(int n)
{
    //初始化
    vector<int> f(n + 1, 0);
    f[0] = 1;
    f[1] = 1;

    //迭代开始
    for (int i = 2; i <= n; ++i)
    {
        for (int k = 1; k <= i; ++k)
        {
            //会用到前面计算出来的值，一维的动态规划
            f[i] += f[k - 1] * f[i - k];
        }
    }
    return f[n];
}

int main()
{
    cout << numTrees(3) << endl;
    return 0;
}

结果输出：