Elegant Java solution with explanation


  • 0
    L

    Others have done more efficient solution using Catalan numbers. This solution uses top-down memoization with recursion. A bottoms-up DP will be better for performance and it should be straight-forward to write in case you want a better performance. I will highlight the idea in this explanation. Here is the summary:

    1. Assuming we have n = 3, it is made of set {1,2,3}. Since we are constructing a BST, we could choose any node as the root and make another set of BSTs from the remaining of the nodes.
    2. So, let us pick up 1 as a root. We will have only one possibility of keeping {2,3} as the right nodes. So the solution for this part will be the no. of unique bsts for n=2
    3. Pick 2 as a root. We will have {1} and {3} as two bsts where each one will have only 1 solution.
    4. Pick 3 as a root. We will have {1,2} as the left children with a count = 2 for n=2.

    This leads to a recursive equation of :
    T(n) =

      for(int i=1;i<=n;i++) {
            //make each one a root.         
            val += T(i-1)*T(n-i);
        }
    

    The base conditions will be T(0)=T(1)=1.

    The code is:

    public int numTrees(int n) {
        //+ve values 
        if(n<=1) {
            return 1;
        }
        int val=0;
        for(int i=1;i<=n;i++) {
            //make each one a root.
            if(map.get(i-1)==null) {
                map.put(i-1,numTrees(i-1));
            }
            if(map.get(n-i)==null) {
                map.put(n-i,numTrees(n-i));
            }
            val += map.get(i-1)*map.get(n-i);
        }
        
        return val;
    }
    

Log in to reply
 

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