鉴于排序的整数数组，您如何从中形成二进制搜索树？

寻找与之相关的问题 MicSim, 我仍然对此感到不满意，所以我开始自己看着他。 这就是我想到的......

每棵树都可以用父根节点查看为两棵树。 如果您单独了解两个子公司可能组合的数量，则具有此根节点的组合总数是子组合的乘积。

我们可以开始以较高的数量建立解决方案，首先求解较低的求解实例。

我会使用

C/n/

代表所有可能的组合 n 结，加泰罗尼亚人。

我希望这两个人很明显：

C/0/ = 1

C/1/ = 1

C/2/ 也很明显，但你可以建立它，所以让我们这样做。 有两种方法可以选择根节点。 一个人离开了孩子的人数 /left:right/ 平等的

1:0

, 和另一个

0:1

. 所以，第一个机会

C/1/*C/0/ = 1*1 = 1

. 和第二 -

C/0/*C/1/ = 1*1 = 1

. 我们一起汇总他们

C/2/ = 2

到目前为止没有什么特别的。 现在让我们这样做 3 节点。 存在 3 选择根节点的方法，因此， 3 子公司。 你可能团体

2:0

,

1:1

和

0:2

.

根据我们之前的定义，

C/3/

你可以写作

C/2/*C/0/ + C/1/*C/1/ + C/0/*C/2/ = 2*1 + 1*1 + 1*2 = 2+1+2 = 5

.

C/3/ = 5

4 节点有子公司

3:0

,

2:1

,

1:2

和

0:3

. 所以，

C/4/

你可以写作

C/3/*C/0/ + C/2/*C/1/ + C/1/*C/2/ + C/0/*C/3/ = 5*1 + 2*1 + 1*2 + 1*5 = 5+2+2+5 = 14

.

C/4/ = 14

我希望两件事开始变得明显。 首先，它很快就会开始变得麻烦。 其次，我所描述的更冗长是在页面上的经常关系的演示 wiki.

我不知道它是否会有所帮助，但它帮助我经历了这项运动，所以我决定分享。 当我开始时，我没有尝试重新创建经常性态度，所以我的结果与现有方法之一相对应。

可以使用的可能性的二进制搜索树数 N 键设置n-m
http://en.wikipedia.org/wiki/Catalan_number
.

另见这个问题：
https://coderoad.ru/1352776/

任何数组节点都可以是root a BST, 对于每个根目录，不同的搜索树的数量是组合 /工作/ 左和右下阶层。 所以，

BSTCount/0/ = 1

BSTCount/n/ = sum_{i = 1}^{n} BSTCount/i-1/ * BSTCount/n-i/

您可以为前几个估计此功能 n, 然后看到序列
http://oeis.org/
, 找到一个封闭的形式。