给定一个已排序的整数数组，可以从中形成多少个二叉搜索树？

Question

假设我有一个数组 [3,18,15,25,26]，那么可以从中形成多少个二叉搜索树？

- Rahul

---

那是作业吗？ - Baz

你正在寻找平衡二叉搜索树吗？ - Peter Lawrey

不，这不是作业。也不是平衡二叉搜索树。 - Rahul

Answer 1

在查看了MicSim提供的链接后，我还是不满意，于是我开始自己研究。以下是我的结论...

每棵树可以被视为具有父节点的两棵子树。如果你知道了两个孩子分支各自的可能组合数，那么拥有该根节点的总组合数就是这些孩子组合的乘积。

我们可以通过先解决较小规模的实例，逐步构建出更高规模的解决方案。

我将使用C(n)来代表n个节点的总可能组合，也就是卡塔兰数。

希望这两个结论很明显：

C(0) = 1
C(1) = 1

C(2)很显然，但它可以被构建，所以让我们来做吧。选择根节点有两种方式。其中一种留下一个子节点计数（左：右）1:0，另一种则是0:1。因此，第一种可能性是C(1)*C(0)=1*1=1。第二种可能性是C(0)*C(1)=1*1=1。将它们相加得到

C(2) = 2

现在还没有太过激动人心的事情。现在让我们做三个节点。选择根节点有三种方式，因此有三种子组合。你可能的组合是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

希望两件事很快变得明显：

1. 这个过程很快就会变得繁琐。
2. 我通过冗长的描述所表达的是维基页面上的递归关系表示法。

我不知道这是否有所帮助，但这个练习对我很有帮助，所以我想分享一下。当我开始时，并没有试图重新创建递归关系，所以很好我的结果与现有方法之一相匹配。

- JerseyMike

---

谢谢解释。确实非常有帮助。 - Rahul

谢谢Mike，这真的很有帮助。我卡在这个问题上了。在这个解释之后，我能够实现这个解决方案了。 - Amber Beriwal

@AmberBeriwal - 我发现将问题分解为其基本部分总是有帮助的。很高兴它对你有用。 :) - JerseyMike

Answer 2

使用N个键可以创建的二叉搜索树的可能数量由第N个卡特兰数给出。

此外，请参见此问题：使用N个键可以创建的二叉搜索树的可能数量由第N个卡特兰数给出。为什么？

- MicSim

Answer 3

数组中的任何一个节点都可以成为二叉搜索树的根节点，对于每个根节点，不同搜索树的数量是左右子数组的组合（乘积）。因此，

BSTCount(0) = 1
BSTCount(n) = sum_{i = 1}^{n} BSTCount(i-1) * BSTCount(n-i)

您可以对前几个n进行评估，然后在整数序列在线百科全书（OEIS）中查找该序列以找到封闭形式。

- thiton