不同的二叉搜索树

96. 不同的二叉搜索树

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

示例 1：

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

提示：

1 <= n <= 19

动态规划

确定dp数组及下标的含义

dp[i]表示：元素值为1到 i 的节点组成的二叉搜索树的个数

确定递推公式

易知，n=1有一棵二叉搜索树，n=2有两颗二叉搜索树，n=3有五颗二叉搜索树，那么dp[3]是怎么来的呢？

如图所示

dp[3]表示元素值为1到3的节点组成的二叉搜索树的数量，等于元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量

元素1为头节点的搜索树数量 = dp[0] * dp[2]

元素2为头节点的搜索树数量 = dp[1] * dp[1]

元素3为头节点的搜索树数量 = dp[0] * dp[2]

故dp[3] = dp[0] * dp[2] + dp[1] * dp[1] + dp[0] * dp[2]

可以确定递推公式

j 从1遍历到 i

dp[i] += dp[j-1] * dp[i-j];

其中dp[ j -1 ]表示 j 个结点不同的左子树，d[i - j ]表示 i - j 个结点不同的右子树

3.初始化dp数组

dp[0] = 1，表示空树只有1颗，若为0后续递归都为0

dp[1] = 1，表示只有1个节点的二叉搜索树只有1颗

确定遍历顺序

先遍历 i ，表示 i 个元素的二叉搜索树，再遍历 j ，用来表示1到 i 里面每一个数作为头节点的情况

for(int i = 2; i <= n; i++){
    for(int j = 1; j <= i; j++){
        dp[i] += dp[j-1] * dp[i-j];
    }
}

代码

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n+1];
        //dp[i]表示i个结点有多少不同二叉搜索树
        dp[0] = 1;
        dp[1] = 1;
        //对于dp[n]，要累加编号[1,n]作为根节点的二叉树数量
        //dp[j-1]表示j-1个结点不同的左子树，d[i-j]表示i-j个结点不同的右子树
        for(int i = 2; i <= n; i++){
            for(int j = 1; j <= i; j++){
                dp[i] += dp[j-1] * dp[i-j];
            }
        }
        return dp[n];
    }
}

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