查找可能的二进制搜索树的数目

Question

假设，我们有钥匙1,2,3,4,5,6,7.我必须找到可能的二进制搜索树的总数，这样二进制搜索树的高度就是6。

答案是64。但我无法找到一个模式，从而从数学上推断出答案。用蛮力画出所有可能的树是不可能的。

可能的树的一个简单例子是倾斜的不平衡树，其中键按升序和降序插入。两棵树的高度都是6，但是如何达到的总和64？

Answer 1

这一点可以通过建筑来证明。

让我们说，

F(n) =高度为n的n+1数的二叉树数

索赔：F(n) = 2^n

证明：

F(0) = 1 (by construction)  
F(1) = 2 (by construction) 

现在，要计算F(n)，那么最小数或最大数都可以是树的根。剩余的n个数字必须排列在左边的子树中(如果最大数是根)，或者右边(如果最小的数是根)。

所以,

F(n) = 2*F(n-1)  
F(n) = 2^n