Non-recursive C solution with comments

  • 1
    int numTrees(int n)
      /*  if (n<=0) return 0; */
      int dp[n+1]; /* dp[i] meaning total # of BST tree with i consecutive nodes */
      memset(dp, 0, sizeof(int)*(n+1));
      dp[0] = 1; /* NULL is one tree */
      for(int i = 1; i<=n; i++)
         /* the idea is for 1....i,  each node can be the root and count the full combination of 
             left sub BST and right sub BST*/
        for(int j = 0; j<i ; j++) 
            dp[i]+= dp[j] * dp[i-j-1];
      return dp[n];

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.