给定数组的多少种排列会产生高度为 2 的 BST？

Question

根据集合 {1,2,3,4,5,6,7} 中键的每个排列生成 BST（通过连续插入节点）。有多少种排列决定高度为二的树？

我在这个简单的问题上被困了很长一段时间。 任何人的任何提示。

顺便说一句，答案是80。

Answer 1

考虑树的高度如何为 2？

-需要有 4 个作为根，2 个作为左子节点，6 个右子节点，等等

为什么4是根？

-它需要是第一个插入的。所以我们现在有一个数字，6 仍然可以在排列中移动。

还有？

-第一次插入后，还剩下 6 个位置，其中 3 个为左子树，3 个为右子树。即 6 选择 3 = 20 个选择。

现在怎么办？

-对于左子树和右子树，需要先插入它们的根，然后子树的顺序不会影响树 - 2, 1, 3 和 2, 3, 1 给出相同的树。每个子树为 2，左右子树为 2 * 2 = 4。

那么？

结论：C(6, 3) * 2 * 2 = 20 * 2 * 2 = 80。

Answer 2

请注意，这棵树只有一种可能的形状 - 它必须完美平衡。 因此它必须是这棵树：

         4
       /   \
      2     6
     / \   / \
    1   3 5   7

这需要先插入4。 之后，插入需要按照正确的顺序构建包含 1、2、3 和 5、6、7 的子树。 这意味着我们需要在 1 和 3 之前插入 2，并且需要在 5 和 7 之前插入 6。我们插入 1 和 3 的相对顺序并不重要，只要它们在 2 之后即可，类似地只要 5 和 7 在 6 之后，我们输入的相对顺序并不重要。因此，您可以将我们需要插入的内容想象为 2 X X 和 6 Y Y，其中 X 是 2 的子级Y 是 6 的子代。然后，我们可以找到所有可能的方法来返回上述树，方法是找到序列 2 X X 和 6 Y Y 的所有交错，然后乘以四（将 X 和 Y 分配给值 1、3、5 和 7）。

那么交错有多少种方式呢？ 好吧，您可以将其视为排列序列 L L L R R R 的方法数量，因为 L L L R R R 的每个排列都告诉我们如何从左序列或右序列中进行选择。 有6个！ /3！ 3！ = 20 种方法可以做到这一点。 由于这 20 个交错中的每一个都给出了四种可能的插入序列，因此最终总共有 20 × 4 = 80 种可能的方法来实现此目的。

希望这有帮助！

Answer 3

我创建了一个表，用于显示 1 - 12 个元素可能的排列数量，高度最多为 12，并包含每个根的细分，供任何试图检查其手动过程（在其他答案中描述）是否匹配的人使用与实际值。

http://www.asmatteringofit.com/blog/2014/6/14/permutations-of-a-binary-search-tree-of-height-x

Answer 4

这是一个帮助接受答案的 C++ 代码，这里我没有显示明显的 ncr(i,j) 函数，希望有人会发现它有用。

int solve(int n, int h) {
    if (n <= 1)
        return (h == 0);

    int ans = 0;

    for (int i = 0; i < n; i++) {
        int res = 0;
        for (int j = 0; j < h - 1; j++) {
            res = res + solve(i, j) * solve(n - i - 1, h - 1);
            res = res + solve(n - i - 1, j) * solve(i, h - 1);
        }
        res = res + solve(i, h - 1) * solve(n - i - 1, h - 1);
        ans = ans + ncr(n - 1, i) * res;
    }
    return ans
}

Answer 5

这棵树必须有 4 作为根，2 和 6 分别作为左子节点和右子节点。根只有一种选择，插入应该从4开始，但是一旦插入根，就会有很多插入顺序。有2种选择，第二次插入2或6。如果第二次插入选择2，则有三种情况选择6：第三次插入选择6，4,2,6,-,-,-,-其余插入有 4!=24 个选择；第四次插入固定 6，4,2,-,6,-,-,- 第三次插入有 2 个选择，1 或 3，还有 3！其余的选择，所以 2*3!=12，最后一种情况是在第五次插入时固定 6，4, 2, -, -, 6, -, - 第三次和第四次插入有 2 个选择（ (1 和 3) 或 (3 和 1)) 以及最后两个插入 ((5 和 7) 或 (7 和 5))，所以有 4 个选择。总共，如果 2 是第二个插入，我们对于其余的插入有 24+12+4=40 个选择。同样，如果第二次插入为 6，则有 40 个选择，因此不同插入顺序的总数为 80。

Answer 6

我们已经知道它应该是完整的二叉搜索树，以4为根，并且每个元素的位置都是固定的。 现在只能更改元素的顺序，例如：2 始终位于 1 和 3 之前，但 1 和 3 可以任意顺序 同样，6 出现在 5/7 之前。

现在我们可以从 2/6 中选择任何一个元素，首先说 2 ： 然后需要为剩下的 5 个元素选择顺序 - - - - -

由于 6 应该出现在 5/7 之前，我们可以以 5C3 的方式从 5 个位置中选取这个固定顺序 3 并乘以 2！适合5/7安排。最后乘以2！用于排列 1/3 .

因此，总路数 = 5C3 * 2 * 2 = 40。

如果先选 6 个，则总方法类似 = 40。

因此，最终总路数 = 40 + 40 = 80。