求解1到n的BST后序遍历合法排列数算法问题求助

核心错误原因 #

你的算法错误地将左右子树的合法BST后序排列数等同于全排列数（阶乘），但实际上，左子树的元素（1_{i）和右子树的元素（i+2}n）各自的合法后序排列数必须是对应节点数的卡特兰数——并非所有排列都符合BST后序的要求。

比如n=4时，你计算的3!+2!+2!+3! = 16是错误的，正确合法数应为卡特兰数C₄=14。这是因为左子树i个节点的合法排列数是卡特兰数Cᵢ，右子树n-1-i个节点的合法排列数是Cₙ₋₁₋ᵢ，而非阶乘。

正确的递推逻辑 #

1到n的BST合法后序排列数等价于第n个卡特兰数，递推规则如下：

• 初始条件：C₀ = 1（空树的合法排列数为1）
• 递推式：Cₙ = Σ（i从0到n-1）Cᵢ × Cₙ₋₁₋ᵢ

解释：选择第i+1个元素作为根节点时，左子树有i个节点，合法排列数为Cᵢ；右子树有n-1-i个节点，合法排列数为Cₙ₋₁₋ᵢ。所有根节点对应的排列数之和即为总合法数。

修正后的代码 #

替换阶乘计算为卡特兰数的递推计算，同时使用long long避免数值溢出（n=20时卡特兰数为6564120420，远超32位int的上限）：

long long catalan(int n) {
    long long cat[n+1];
    cat[0] = 1;
    cat[1] = 1;
    for (int i = 2; i <= n; i++) {
        cat[i] = 0;
        for (int j = 0; j < i; j++) {
            cat[i] += cat[j] * cat[i-1-j];
        }
    }
    return cat[n];
}

// 调用示例：catalan(3) 返回5，catalan(4)返回14

验证示例 #

• n=3时：C₃ = C₀×C₂ + C₁×C₁ + C₂×C₀ = 1×2 +1×1 +2×1 = 5，与你给出的正确结果一致。
• n=4时：C₄ = C₀×C₃ + C₁×C₂ + C₂×C₁ + C₃×C₀ =1×5 +1×2 +2×1 +5×1=14，这才是正确的合法排列数。

额外注意事项 #

• n≤20时，64位long long可以容纳所有卡特兰数；若需计算更大的n，需使用高精度整数实现。

内容的提问来源于stack exchange，提问作者mmdmxi