📃 题目描述

题目链接：96. 不同的二叉搜索树 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

输入：n = 3
输出：5

🔔 解题思路

dp[i] 表示 节点值从 1 到 i 互不相同的 二叉搜索树 有 dp[i] 种

这么说描述 dp[i] 其实不太好理解下面的状态转移方程，我们换个说法：dp[i] 表示有 i 个节点的互不相同的二叉搜索树有 dp[i] 种

dp[i] += dp[以 j 为头结点左子树节点数量] * dp[以 j 为头结点右子树节点数量]

（j 相当于是头结点的元素，从1遍历到 i 为止）

• 以 j 为头结点左子树节点数量 = j - 1
• 以 j 为头结点右子树节点数量 = i - j

=> 所以递推公式：dp[i] += dp[j - 1] * dp[i - j]

base case:

• dp[0] = 1 这个很容易被忽略。如果 dp[0] = 0 的话，一旦左子树或者右子树上没有节点，那么相乘的结果就是 0 了，显然不符合
• dp[1] = 1,dp[2] = 2，这两个很容易得到

事实上，dp[2] = 2 这个 base case 都是不需要的，它可以通过 dp[0] 和 dp[1] 得到

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];

        // base case
        dp[0] = 1;
        dp[1] = 1;

        // loop
        for (int i = 2; i <= n; i ++) {
            // 以 j 为头节点
            for (int j = 1; j <= i; j ++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }

        return dp[n];
    }
}

二刷的时候写了一个更泛化的解法：

class Solution {
    public int numTrees(int n) {
        if (n == 1) {
            return 1;
        }

        int[] dp = new int[n + 1];

        // base case
        dp[0] = 1;

        // i 表示所有节点的个数
        for (int i = 1; i <= n; i ++) {
            // j 表示左子树的节点个数，那么右子树的节点个数就是 i - j - 1
            for (int j = 0; j < i; j ++) {
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }

        return dp[n];
    }
}

]()

💥 复杂度分析

• 空间复杂度：O(N)
• 时间复杂度：O(N^2)