ATTENTION: adding five lines code can help reducing running time from 1140ms to 4ms!!!!


  • 7
    B

    if you comment the code between //code-start and //code-end, the running time will up to exceed 1000ms.
    this code avoid redundant calculation of the same size BST, because any sequence with the same size has the same BST number. for example, {1,2,3} has 5 BST, so does {1,2,4},{4,5,6}, ...{a,b,c}...

    class Solution {
    public:

    int divideTrees(int start, int end, map<int,int> &mp)
    {
        if(start >= end)
        {
            return 1;
        }
        int k = end-start+1;
        //code-start
        if(mp.find(k) != mp.end())
        {
            return mp[k];
        }
        //code-end
        int res = 0;
        for(int i = start; i <= end; ++i)
        {
            int res1 = divideTrees(start, i-1, mp);
            int res2 = divideTrees(i+1,end,mp);
            res += res1*res2;
            mp[i-1-start+1] = res1;
            mp[end-i-1+1] = res2;
        }
        return res;
    }
    int numTrees(int n) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        map<int,int> mp;
        mp[1] = 1;
        mp[2] = 2;
        return divideTrees(1,n,mp);
    }
    

    };


  • 0
    S

    Could you please edit your code format? some part of your code is out of code box.


  • 11
    W

    Ben, do you really need a map here. If you have to, you can try unordered map, instead of map. Unordered map supposes having O(1) searching time, while map is O(logN).

    The most elegant code is as below, but you need prepare to explain why this is a Catalan_number. (http://en.wikipedia.org/wiki/Catalan_number)

    class Solution {
    public:
        int numTrees(int n) {
            // IMPORTANT: Please reset any member data you declared, as
            // the same Solution instance will be reused for each test case.
    		if(n == 0 || n == 1 || n == 2)
    			return n;
    		int results=2;
    		for(int i=3; i<=n; i++)
    			results=results*2*(2*i-1)/(i+1);
    		return results;
    	}
    };

  • 0
    P

    Either map or unordered_map is acceptable because N is small in this case.


  • 0
    B

    yeh, that absolutely is the least code for this problem. but i think you may need to deduce this formula to the interviewer , just give the answer is apparently not enough.
    I tried, but failed. :)


  • 0
    S

    If you want an explanation of the formula, this link will greatly help:
    [http://cs.lmu.edu/~ray/notes/binarytrees/] 1


  • 0
    X

    I also cached calculated value. But I only got 348ms. Is it because I used Java instead of C++?

    public class Solution {
    private int[] cache;

    private int numTrees_helper(int n) {
        if (n == 0) return 1;
        if (n == 1) return 1;
        if (cache[n] != 0) return cache[n];
        int count = 0;
        for (int i = 0; i < n; i++) {
            count += numTrees_helper(i) * numTrees_helper(n - i - 1);
        }
        cache[n] = count;
        return count;
    }
    
    public int numTrees(int n) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        cache = new int[n + 1];
        return numTrees_helper(n);
    }
    

    }


  • 0
    F
    if (n < 1)
    	return 0;
    else if (n < 3)
    	return n;
    else if (n == 3)
    	return 5;
    else
    	;
    
    vector<int> numNodes(n+1);
    numNodes[0] = 1;
    numNodes[1] = 1;
    numNodes[2] = 2;
    numNodes[3] = 5;
    
    for (int i = 4; i <= n; i++)
    {
    	int num = 0;
    	int j = 1;
    	for (; j <= i/2; j ++)
    	{
    		int leftnodes = numNodes[j-1];
    		int rightnodes = numNodes[i-j];
    		num = num + (leftnodes * rightnodes);
    	}
    	num *= 2;
    	if (i % 2 != 0)
    	{
    		int lfn = numNodes[j-1];
    		int rhn = numNodes[i-j];
    		num = num + (lfn * rhn);
    	}
    
    	numNodes[i] = num;
    }
    
    return numNodes[n];
    

    here is the 4ms answer.if u use k (0< k <= n) as root, the numTrees is his left child nodes multiply right child nodes . and u can store 1,2..k-1 ....


  • 24
    G

    I use below code running only for 4 ms:

    int numTrees(int n) 
    {
        if(n<0) return 0;
        
        vector<int> result;
        result.push_back(1);
        result.push_back(1);
        
        for(int k=2;k<=n;k++)
        {
            int sum=0;
            for(int i=1;i<=k;i++)
            {
                sum+=(result[i-1]*result[k-i]);
            }
            
            result.push_back(sum);
        }
        
        return result[n];
    }

  • 0
    S

    Hi @gh, thanks for your sharing. Could you please try to add some words about your algorithm or comments in code would be more helpful for others?


  • 0
    M
    This post is deleted!

  • 0
    D

    Well, mine has comment in it and it's the same as this post, so just share it with you here. It certainly could be further optimized that these two cases could be only calculated once and directly multiply by 2: 1) left subtree has x nodes and right subtree has y nodes; 2) left subtree has y and right subtree has x.

    /**
     * Solution:
     * DP
     * a BST can be destruct to root, left subtree and right subtree.
     * if the root is fixed, every combination of unique left/right subtrees forms
     * a unique BST.
     * Let a[n] = number of unique BST's given values 1..n, then
     * a[n] = a[0] * a[n-1]     // put 1 at root, 2...n right
     *      + a[1] * a[n-2]     // put 2 at root, 1 left, 3...n right
     *      + ...
     *      + a[n-1] * a[0]     // put n at root, 1...n-1 left
     */
    int numTrees(int n) {
        if (n < 0) return 0;
        vector<int> trees(n+1, 0);
        trees[0] = 1;
    
        for(int i = 1; i <= n; i++) 
            for (int j = 0; j < i; j++) 
                trees[i] += trees[j] * trees[i-j-1];
        
        return trees[n];
    }
    

  • 0
    J

    when n == 0 why it returns 1. I know this would be helpful in the process of recursive , but is it a wrong answer?.


  • 3
    D
    public class Solution {
    public int numTrees(int n) {
        int[] no = new int[n+1];
        no[0] = 1;
        no[1] = 1;
        for(int i = 2 ; i <= n; i++)
         for (int j = 0; j < i; j++)
            no[i] = no[i] + no[j] * no[i-j-1];
            
        return no[n];
        
    }
    

    }

    I also got 344ms, is it possible for java to get 4ms?


  • 0
    C

    can you correct the link? it's http://en.wikipedia.org/wiki/Catalan_number


  • 2
    L

    Is is a catalan number(http://en.wikipedia.org/wiki/Catalan_number)
    I use following code to pass the test case.

    class Solution {
    public:
        int numTrees(int n) {
            long long ans = 1;
            for(int i = 1; i <= n; ++ i)
                ans  = ans * 2 * (2 * i - 1) / (i + 1);
            return (int) ans;
        }
    };

  • 0
    O
    This post is deleted!

  • 0
    S
    This post is deleted!

  • 0
    L

    @dragonmigo Thanks for sharing. This is really nice code. Only a little confused by the a[0]'s meaning.
    In your comment it seems a[0] refers to case 1. If so, a[n-1] should refer to case 1...n rather than the case 2...n. Is my thinking wrong?


  • 0
    K

    Imagine a tree with no node, then there is a root reference/pointer which is null. You can't say the tree doesn't exist and has no structure, right?


Log in to reply
 

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