No tricks java naive solution using recursion and DP. - 0 ms


  • 0
    S

    The main and natural idea of this solution is to go through vertices and calculate number of combinations 'k' for each of them. k = kLeft * kRight.
    Use cache to speed up recursion.

    public class Solution {
    	private int[] cache = new int[100]; 
        public int numTrees(int n) {
    		if(cache[n]>0){
    			return cache[n];
    		}
    		int k = 0;
            for(int i = 1; i<= n; i++){
    			k+=Math.max(1,numTrees(i-1))*Math.max(1,numTrees(n-i));
    		}
    		cache[n]=k;
    		return k;
        }
    }

Log in to reply
 

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