Simple C++ code with explaination. 0ms


  • 0
    J
    class Solution{
        unordered_map<int, int> res;
    public:
        int numTrees(int n){
            if (n <= 0 || n == 1)
                return max(n, 0);
    
            int ret = 0;
            for(int i = 1; i <= n; i++){
                if(i == 1 || i == n){
                    int first = 0, second = 0;
                    if(res.find(n - 1) == res.end()){
                        first = numTrees(n - 1);
                        res[n - 1] = first;
                    }else
                        first = res[n-1];
                    ret += first;
                }
                else{
                    int first = 0, second = 0;
                    if(res.find(i - 1) == res.end()){
                        first = numTrees(i - 1);
                        res[i - 1] = first;
                    }else
                        first = res[i-1];
                    if(res.find(n - 1) == res.end()){
                        second = numTrees(n - i);
                        res[n-i] = second;
                    }else
                        second = res[n-i];
                    ret += first * second;
                }
            }
            return ret;
        }
    };
    

    the idea is :
    using an hashmap to store the numTrees that have been calculated to aviod repeat calculation

    1. the elements are not repeated
    2. any elements of 1~n can be the root
    3. the root, i , has one/ two children, left :(0~i-1) , right : (i + 1
      ~ n), at this situation, the numTree of this root is numTree(i - 1)
      * numTree(n - i ). if i == 1 or i == n, it's numTree(n - 1)
    4. use a hashmap to store previously calculated numTrees to avoid redundant calculation

  • 0
    V

    Time limit exceeded when n=19.


  • 0
    Q

    Time is not 4ms!!


  • 0
    V

    Test data have been updated already.


  • 0
    Q

    thank you for your reply!


  • 0
    E

    This recursive code will recalculate numTrees( ) every time it's called. Should use some container to store the previous result, so as to avoid the redundant calculation.


  • 0
    J

    yes , an hashmap should be good for this problem


  • 0
    J

    leetcode has updated the testing instances, so I changed my code to avoid TLE, and it's quick enough. thank you


Log in to reply
 

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