LeetCode96：不同的二叉搜索树

题目：给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

思路：来源于carl和powcai
1、有n个节点，设一共存在的二叉排序数的个数是dp[n]，其中j为根节点时,二叉排序数的个数为f(j)；则dp[n]=f(1)+f(2)+…+f(n)；
2、由于二叉搜索树的左子树均小于根节点，右子树均大于根节点，所以当j为根节点时，左子树的个数为[1,…,j-1]，右子树的个数为[j+1,…,n]；
则左子树可以组成的二叉搜索树的个数为：dp[j-1]=f(1)+f(2)+…+f(j-1)；
右子树可以组成的二叉搜索树的个数为：dp[n-j]=f(1)+f(2)+…+f(n-j)；
则当前共有i个节点，j为根节点时，可以组成的二叉搜索树的个数为：dp[i]=dp[j-1]*dp[i-j]；
其中dp[j-1]和dp[i-j]已经由前面的dp[i]计算出来了(所以需要计算仅有i个节点时可组成的二叉搜索树的个数)。

(carl)解题步骤：
1、将n个节点可以组成的二叉搜索树的个数,转化为1-n个节点分别可以组成的个数。

for(int i=1;i<=n;i++)

2、n个节点可以组成的个数为 以每个节点值为根节点所可以组成的二叉搜索树的个数。

for(int j=1;j<=i;j++)

3、以每个节点值为根节点所可以组成的二叉搜索树的个数为 左子树的节点个数可组成的树的个数*右子树的节点个数组成数的个数。

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

代码如下：

class Solution {
public:
    // 将n个节点可以组成的二叉搜索树的个数,转化为1-n个节点分别可以组成的个数
    // n个节点可以组成的个数为 以每个节点值为根节点所可以组成的二叉搜索树的个数
    // 以每个节点值为根节点所可以组成的二叉搜索树的个数为 左子树的节点个数可组成的树的个数*右子树的节点个数组成数的个数
    int numTrees(int n) {
        // 因为i可以到n,所以dp数组在进行初始化时的size为n+1
        // dp[i]:1-i个节点所能组成的二叉搜索树的个数
        vector dp(n+1);
        dp[0]=1;  // 根据定义,0个节点时也是一个二叉搜索树

        // 这里的循环i代表由1-i个节点组成的二叉搜索树的个数  因为需要计算左子树和右子树可以组成的个数(拆分为子问题了)
        // j为组成二叉搜索树的根节点:由1-i 
        for(int i=0;i<=n;i++){
            for(int j=1;j<=i;j++){
                // dp[j-1]*dp[i-j]:j为根节点时,左子树和右子树的节点数量
                // 由这些节点组成的二叉树的个数 已经由dp[i]计算过了
                dp[i]+=dp[j-1]*dp[i-j];
            }
        }
        return dp[n];
    }
};