Unique Binary Search Trees

32%

Accepted

Given n, how many structurally unique BSTs (binary search trees) that store values 1...n?

Have you met this question in a real interview? 

Yes

Example

Given n = 3, there are a total of 5 unique BST's.

1           3    3       2      1
 \         /    /       / \      \
  3      2     1       1   3      2
 /      /       \                  \
2     1          2                  3




public class Solution {
    /**
     * @paramn n: An integer
     * @return: An integer
     */
    public int numTrees(int n) {
        // write your code here
       return counting(1, n);
    }
   
    private int counting(int left, int right){
        if(left >= right) return 1;
        int count = 0;
        for(int i = left; i <= right; i++){
            count += counting(left, i-1) * counting(i+1, right);
        }
        return count;
    }
   
   
}

catalan==>

public class Solution {
    /**
     * @paramn n: An integer
     * @return: An integer
     */
    public int numTrees(int n) {
      if(n <= 0) return 1;
      int[] record = new int[n+1];
     
      record[0] = 1;
      record[1] = 1;
      for(int i = 2; i <= n; i++){
          for(int j = 0; j < i; j++){
              record[i] += record[j] * record[i-j-1];
          }
      }
      return record[n];
    }
   
   
}