结题思路：假设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];
  }
}