Leetcode-Unique Binary Search Trees in Java

問題

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

For example,

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


這題跟一個離散數學的觀念有關

就是Catalan Number

是一個很神奇的數字

它的表示可以是如此



任何能夠表達成上列這樣形式的問題都可以套入Catalan 公式求解

有五六十個例子，所以才說他很神奇

例如：

1.是一個有n個X和n個Y組成的字串，且所有的前綴字串皆滿足X的個數大於等於Y的個數

2.n組括號的合法運算式

3.在方陣從(0,0)走到(n,n)的方法數 


有興趣請參照以下部落格

https://johnmayhk.wordpress.com/2014/02/03/cn/

然後就是本題的 n 個node的話，有幾種異構二元樹

想看看n個點要不都是左，要不就是右

左邊1個點，右邊就是n-1(這個1)-1個點去排樹

左邊兩個點，右邊就是n-1-2個點去排樹

所以就跟上面那個Catalan的式子符合

C0的話就是 沒有點，那就是空樹，答案是1

C1就是只有一個點，那也是1，只有一種樹


所以這樣就可已寫了

下面有兩種方法來寫


1.Recursive

遞迴來寫很簡單

public class Solution {
    public int unqbntree(int n) {
        
        if(n==0||n==1)
           return 1;
        
        int sum=0;
  
        for(int i=1;i<=n;i++)
         sum+=unqbntree(n-i)*unqbntree(i-1);
      
        return sum;
    }

不過妳可以發現，重複做到了很多次，浪費了時間


2. DP

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

其實就拿空間換時間而已 想最快的話就套公式 不過面試官看了應該會吐血就是了。