Easy to read DP solution though not the first to the party


  • 2
    K
    // DP solution based upon the idea that the number of trees with "n" elements is
    // related to the number of left and right subtrees that can be constructed
    // using 0 to n-1 elements.
    
    public int numTrees(int n) {
    
        int[] trees = new int[n+1];
        trees[0] = 1;
        trees[1] = 1;
    
        for (int tree=2; tree <= n; tree++) {
            int numTrees = 0;
            for (int i=1; i <= tree; i++) {
                int numLTrees = trees[i-1];
                int numRTrees = trees[tree-i];
                numTrees += numLTrees * numRTrees;
            }
            trees[tree] = numTrees;
        }
        
        return trees[n];
    }

  • 0
    K

    Why the down vote? Is there something wrong with this solution?


Log in to reply
 

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