每日算法 — 使用java实现不同的二叉搜索树：卡特兰数与区间动态规划

问题描述

给定一个整数 n，求以 1 到 n 为节点组成的不同的二叉搜索树（BST）有多少种？

二叉搜索树的定义是：对于树中的任意节点，其左子树中所有节点的值都小于该节点的值，右子树中所有节点的值都大于该节点的值。由于节点值固定为 1 到 n，树的形状不同即代表不同的 BST。

例如，当 n = 3 时，共有 5 种不同的 BST：

  1         3     3      2      1
   \       /     /      / \      \
    3     2     1      1   3      2
   /     /       \                 \
  2     1         2                 3

核心思路：区间动态规划

关键观察

假设我们选择数字 i 作为根节点（1 <= i <= n）：
– 左子树必须由 1 到 i-1 的数字组成，共有 dp[i-1] 种构造方式。
– 右子树必须由 i+1 到 n 的数字组成，共有 dp[n-i] 种构造方式。
– 根据乘法原理，以 i 为根的不同 BST 数量为 dp[i-1] * dp[n-i]。

状态转移方程

$$dp[n] = \sum_{i=1}^{n} dp[i-1] \times dp[n-i]$$

其中 dp[0] = 1（空树也是一种有效结构），dp[1] = 1（只有一个节点）。

与卡特兰数的关系

这个递推公式正是卡特兰数（Catalan Number）的定义！第 n 个卡特兰数的值为：

$$C_n = \frac{(2n)!}{(n+1)! \times n!}$$

因此，不同的 BST 数量等于第 n 个卡特兰数。

完整Java实现

/**
 * 不同的二叉搜索树计数问题
 * 使用区间动态规划求解，本质上是计算卡特兰数
 */
public class UniqueBinarySearchTrees {

    /**
     * 方法一：动态规划（自底向上填表）
     * 时间复杂度: O(n^2)，空间复杂度: O(n)
     *
     * @param n 节点数量（值为1到n）
     * @return 不同的BST数量
     */
    public int numTreesDP(int n) {
        // dp[i] 表示由i个节点组成的不同BST的数量
        int[] dp = new int[n + 1];

        // 基础情况：空树有1种构造方式
        dp[0] = 1;
        // 只有一个节点时，只有1种BST
        dp[1] = 1;

        // 自底向上计算：先算2个节点，再算3个节点，直到n个节点
        for (int nodes = 2; nodes <= n; nodes++) {
            // 枚举每个数字作为根节点
            for (int root = 1; root <= nodes; root++) {
                // 左子树有 root-1 个节点，右子树有 nodes-root 个节点
                // 根据乘法原理，以当前root为根的BST数量为两者的乘积
                dp[nodes] += dp[root - 1] * dp[nodes - root];
            }
        }

        return dp[n];
    }

    /**
     * 方法二：数学公式法（卡特兰数直接计算）
     * 时间复杂度: O(n)，空间复杂度: O(1)
     *
     * 卡特兰数公式: C(n) = (2n)! / ((n+1)! * n!)
     * 为了避免大数溢出，使用递推公式: C(n) = C(n-1) * 2(2n-1) / (n+1)
     */
    public int numTreesMath(int n) {
        // 使用long防止中间计算溢出
        long result = 1;

        // 递推计算卡特兰数
        // C(0) = 1
        // C(n) = C(n-1) * 2 * (2n - 1) / (n + 1)
        for (int i = 1; i <= n; i++) {
            result = result * 2 * (2 * i - 1) / (i + 1);
        }

        return (int) result;
    }

    /**
     * 方法三：记忆化搜索（自顶向下递归）
     * 适合理解递归结构，但效率不如自底向上DP
     */
    public int numTreesMemo(int n) {
        int[] memo = new int[n + 1];
        memo[0] = 1;
        memo[1] = 1;
        return countTrees(1, n, memo);
    }

    private int countTrees(int start, int end, int[] memo) {
        // 区间为空，返回1（空树）
        if (start > end) {
            return 1;
        }

        int nodes = end - start + 1;
        // 如果已经计算过，直接返回
        if (memo[nodes] != 0) {
            return memo[nodes];
        }

        int total = 0;
        // 枚举当前区间中的每个值作为根节点
        for (int root = start; root <= end; root++) {
            // 左子树的取值范围: [start, root-1]
            int leftTrees = countTrees(start, root - 1, memo);
            // 右子树的取值范围: [root+1, end]
            int rightTrees = countTrees(root + 1, end, memo);
            // 乘法原理：左右子树组合数相乘
            total += leftTrees * rightTrees;
        }

        memo[nodes] = total;
        return total;
    }

    /**
     * 扩展：返回所有具体的BST结构（而不仅仅是数量）
     * 使用递归构造所有可能的树
     */
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new ArrayList<>();
        }
        return buildTrees(1, n);
    }

    private List<TreeNode> buildTrees(int start, int end) {
        List<TreeNode> result = new ArrayList<>();

        if (start > end) {
            result.add(null); // 空树
            return result;
        }

        for (int rootVal = start; rootVal <= end; rootVal++) {
            // 递归构建左子树所有可能的结构
            List<TreeNode> leftTrees = buildTrees(start, rootVal - 1);
            // 递归构建右子树所有可能的结构
            List<TreeNode> rightTrees = buildTrees(rootVal + 1, end);

            // 组合左右子树与根节点
            for (TreeNode left : leftTrees) {
                for (TreeNode right : rightTrees) {
                    TreeNode root = new TreeNode(rootVal);
                    root.left = left;
                    root.right = right;
                    result.add(root);
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        UniqueBinarySearchTrees solution = new UniqueBinarySearchTrees();

        // 测试不同节点数量的情况
        for (int n = 1; n <= 10; n++) {
            int dpResult = solution.numTreesDP(n);
            int mathResult = solution.numTreesMath(n);
            int memoResult = solution.numTreesMemo(n);

            System.out.printf("n=%2d: DP=%7d, Math=%7d, Memo=%7d%n",
                    n, dpResult, mathResult, memoResult);
        }

        // 输出前10项卡特兰数：
        // n= 1: 1
        // n= 2: 2
        // n= 3: 5
        // n= 4: 14
        // n= 5: 42
        // n= 6: 132
        // n= 7: 429
        // n= 8: 1430
        // n= 9: 4862
        // n=10: 16796
    }
}

复杂度分析

扩展思考

1. 不同的BST II：不仅要计算数量，还要返回所有具体的树结构。这正是代码中 generateTrees 方法实现的功能。
2. 卡特兰数的其他应用：合法的括号序列数、栈的出栈序列数、凸多边形的三角划分数等。
3. 大数处理：当 n 较大时（如 n > 19），结果会超过 int 范围，需要使用 long 或 BigInteger。

总结

不同的二叉搜索树问题巧妙地将区间动态规划与卡特兰数联系在一起。通过枚举根节点、分解左右子问题的思路，我们得到了优雅的递推公式。掌握这一思想，不仅能够解决 BST 计数问题，还能加深对递归分解和动态规划本质的理解。