1ms in C++ By Using Theorem From Graph Theory


  • 0
    Y
    class Solution {
    public:
    	int numTrees(int n) {
    		long long result = 1;
    		long long temp = 1;
    		for(int i = 2*n; i > n; i--){
    			result *= i;
    			temp *= (i-n);
    			if (result % temp == 0){
    				result /= temp;
    				temp = 1;
    			}
    		}
    		return result/(n+1);
    	}
    

    };

    This is my code. I use the property that the number of unique binary trees or n vertex is

    {(2n)(2n-1)(2n-2)....(n+2)}/{(n)(n-1)....(2)(1)}


  • 0
    B

    Would please give a proof of the formula or a lien or a reference book or article.
    Thank you!


  • 0
    W

    Here you go: https://en.wikipedia.org/wiki/Catalan_number Actually, you only need the recurrence relation, then just memoize.


Log in to reply
 

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