96. Unique Binary Search Trees.md

96. Unique Binary Search Trees

---

leetcode Daily Challenge on June 24, 2020.

leetcode-cn Daily Challenge on July 15, 2020.

---

Difficulty : Medium

Related Topics : Tree、Dynamic Programming

---

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

Example:

Input: 3
Output: 5
Explanation:
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

---

Solution

• mine
  • Java
    • DP Bottom-Up Runtime: 0 ms, faster than 100.00%, Memory Usage: 36.3 MB, less than 33.21% of Java online submissions

      // O(N^2)time O(N)space
      public int numTrees(int n) {
          // f(0) = 1 f(1) = 1 f(2) = 2
          // f(n) = f(0) * f(n-1) + f(1) * f(n-2) + .... + f(n-1) * f(n-1 - (n-1))
          // f(3) = f(0) * f(2) + f(1) * f(1) + f(2) * f(0)
          if(n < 2){
              return n;
          }
          int[] dp = new int[n + 1];
          dp[0] = 1;
          dp[1] = 1;
          for(int i = 2; i <= n; i++){
              for(int j = 0; j < i; j++){
                  dp[i] += dp[j] * dp[i - 1 - j];
              }   
          }
          return dp[n];
      }
      

---

• leetcode solution
  • Math - Catalan Number wiki link Runtime: 0 ms, faster than 100.00%, Memory Usage: 35.6 MB, less than 99.88% of Java online submissions

    //O(N)time O(1)space
    
    //h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)*h(0) (n>=2)
    //h(n)=h(n-1)*(4*n-2)/(n+1);
    //h(n)=C(2n,n)/(n+1) (n=0,1,2,...)
    //h(n)=c(2n,n)-c(2n,n-1)(n=0,1,2,...)
    public int numTrees(int n) {
     // Note: we should use long here instead of int, otherwise overflow
      long C = 1;
      for (int i = 0; i < n; ++i) {
        C = C * 2 * (2 * i + 1) / (i + 2);
      }
      return (int) C;
    }
    

---