96. 不同的二叉搜索树

结题思路：假设n个节点存在二叉排序树的个数是G(n)，1为根节点，2为根节点，...，n为根节点，当1为根节点时，其左子树节点个数为0，右子树节点个数为n-1，同理当2为根节点时，其左子树节点个数为1，右子树节点为n-2，所以可得G(n) = G(0) * G(n-1)+G(1)* G(n-2)+...+G(n-1)* G(0)

class Solution {
    public int numTrees(int n) {
        if(n==0)return 1;
        int [] ans = new int[n+1];
        ans[0] = 1;
        ans[1] = 1;
        for (int i = 2; i <= n; i++) {
            for(int j = 1 ; j <= i ;j++){
                ans[i] += ans[j-1]*ans[i-j];
            }
        }
        return ans[n];
    }
}

第二种方法也是动态规划，建立dp矩阵，dp[i]代表i个节点能组成多少种二叉搜索树，将dp[0]、dp[1]置为1。然后dp[n]的值为多少呢？

• 假设以节点值i为根节点(i<=n)，那么左子树的节点就为 [公式] ,右子树的节点为 [公式] 。
• 对于某一个根节点i，假设其左子树的组成方式为left种,右子树的组成方式为right种，那么他们一共可以组成 [公式] 种二叉搜索树。
• 所以dp[n]就为将左边子树的节点数为分别设置为0个到n-1个时(要有一个根节点)，这些情况下左右子树的组成方式之积的和。

  class Solution {
    public int numTrees(int n) {
        int [] dp = new int[n+1];
        dp[0]=1;
        dp[1]=1;
        //计算dp矩阵的值。
        for(int i=2;i<=n;++i)
        {
            //左右子树一一对应，故是乘法。
            for(int l=0;l<=i-1;++l)//左边子树的节点数为0个到i-1个，因为第i个为根节点。
                dp[i]+=dp[l]*dp[i-l-1];
        }
        return dp[n];
    }
  }