algorithm - 通过插入 11 个节点得到一棵高度为 3 的树，你可以创建多少个 BST？

Question

从集合中的每个键的排列中生成(通过连续插入节点)BST

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}.

有多少排列决定了高度为三的树？

Answer 1

您必须检查的节点排列数是 11! = 39,916,800，所以你可以编写一个程序来暴力破解它。这是一个用 C++ 编写的框架:

vector<int> values = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
unsigned numSuccesses = 0;
do {
    if (bstHeightOf(values) == 3) values++;
} while (next_permutation(values.begin(), values.end());

在这里，您只需要编写bstHeightOf 函数，计算按指定顺序插入给定节点形成的BST 的高度。我将把它留作练习。

您可以通过使用这些观察结果来减少搜索空间:

1. 高度为 2 的 BST 中的最大节点数为 7。
2. 根不能是 1、2、3、9、10 或 11，因为如果是，一棵子树中的节点将超过 7 个，因此整棵树的高度将大于 3。

鉴于您知道可能的根，一种选择是使用键 {1, 2, 3, ..., 11} 生成所有 BST(不是通过列出所有顺序，而是通过列出所有树) ，将其过滤到高度为 3 的节点集，然后使用 this recursive algorithm通过插入值来计算每棵树的构建方式的数量。这可能比上述方法快得多，因为要检查的树的数量远低于排序的数量，并且可以在线性时间内检查每棵树。

希望这对您有所帮助!