具有相同DFS阶数的树的数量？

Question

假设我们有一棵树（不一定是二叉树），根节点标记为1。如何知道具有相同DFS阶数的树的确切数量？

例如，如果我们进行 DFS 遍历：{1, 2, 3}，那么答案就是 2，因为我们有两棵树：{(1, 2), (2, 3)} 和 {(1, 2) ), (1, 3)}

我很好奇我们如何用最大节点数来有效地计算它<= 100. I appreciate for your help!!

编辑：我错过的另一件事是这个 DFS 顺序并不是完全随机的。它确保如果有多个节点具有不同的值，它将按升序调用这些节点。

Answer 1

幸运的是，我已经找到了解决方案。不过，感谢大家抽出时间来完成此任务。

实际问题需要以 10 ^ 9 + 7 为模得到答案，因此生成所有可能的树并不是一个好主意，因为数量会很大。相反，我们将查看 DFS 的顺序来决定如何构建这棵树。

考虑 DFS 为 [1,2,4,3] 的情况。如果您尝试绘制符合此顺序的所有 3 棵树，您将看到该图案。具体来说，不存在像{(1, 2), (1, 4), (1, 3)}这样的树，因为如果有的话，顺序将是[1,2,3,4]。可以看到，如果将(1,4)视为一条边，那么必须立即将(4,3)作为下一条边，否则DFS顺序将在调用节点4之前调用节点3。另一件事是也就是说，如果某些节点位于同一子树中，那么按照 DFS 顺序，它们将是相邻的。

这就是我的全部观察。现在，为了计算答案，我将考虑如何将数组划分为子树。让我们考虑一个更大的输入，例如 [1,2,4,5,7,3,8,6]。 1 将是根，所以我们将忽略它。剩下的，我将决定如何将节点划分为子树，然后将有多种方法。以下是一些可能的划分方法：{(2,4), (5,7,3,8,6)}, {(2,4,5), (7,3,8,6)}, { (2), (4), (5), (7), (3), (8), (6)} （如下图所示）。请注意，像 {(2), (4,5,7), (3,8,6)} 这样的除法是无效的，因为第二个子树的根是 4，它比第三个子树的根大（ 4 > 3)，并且它不会遵循初始的 DFS 顺序，因为 3 将在 4 之前调用。在我们划分了连接到根 1 的节点之后，我们现在唯一要做的就是递归计算有效树的数量在每个子树中，然后将它们相乘即可得到答案。

由于会有很多重叠，我们可以使用DP来优化上面的解决方案。时间复杂度对我来说很难估计，因为我不知道如何计算将数组划分为子树时的复杂度。不过，我用 n = 100 运行，看起来很快，所以没问题。

Answer 2

换句话说，这是计算具有给定节点数的有序树的问题。

这与加泰罗尼亚数字有关。在示例列表中，维基百科指出：

C_n 是具有 n + 1 个顶点的非同构有序（或平面）树的数量。

因此问题归结为有效计算加泰罗尼亚数字。我们可以使用多种方法来做到这一点。例如，我们可以使用这个递归关系：

      𝐶₀ = 1

      𝐶_𝑛 = 2(2𝑛 − 1) 𝐶_𝑛−1 / (𝑛 + 1)

包含一些结果的表格：

𝑛 = 节点数	𝐶𝑛−1 = 具有 𝑛 节点的有序树数量
1	1
2	1
3	2
4	5
5	14
6	42

例如用 JavaScript 实现：

const memo = [1];

function C(n) {
    if (!memo[n]) memo[n] = 2 * (2*n - 1) * C(n-1) / (n + 1); // Only calculate once
    return memo[n]; 
}

function numberOfOrderedTrees(n) {
    return C(n-1);
}

// Example for n = 6
console.log(numberOfOrderedTrees(6));  // 42