algorithm - 给定数组的多少排列导致 BST 的高度为 2？

Question

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

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

顺便说一句，答案是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 之后，类似地只要它们在 6 之后，我们将 5 和 7 放入什么相对顺序无关紧要。因此，您可以将我们需要插入的内容视为 2 XX 和 6 YY，其中 X 是 2 的孩子，而Y 是 6 的孩子。然后我们可以找到所有可能的方法来返回上述树，方法是找到序列 2 XX 和 6 YY 的所有交错，然后乘以 4（分配 X 和 Y 值的方法数 1 , 3, 5, 和 7)。

那么有多少种交错方式呢？好吧，您可以将其视为排列序列 LLLRRR 的方法的数量，因为 LLLRRR 的每个排列都告诉我们如何从左序列或右序列中进行选择。有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
}