Java solution


  • 0
    V
    public class Solution {
        public int numTrees(int n) {
            if (n < 3) return n;
            int trees[] = new int[n + 1]; // extra space for n=0
            trees[0] = 1; // we can create one empty tree with n = 0
            trees[1] = 1; // we can create one tree with n = 1
            trees[2] = 2; // we can create two trees with n = 2
            for (int numNodes = 3; numNodes <= n; numNodes++) { 
                for (int nodesOnLeft = 0; nodesOnLeft < numNodes; nodesOnLeft++) {
                  // imagine a tree with a root, some elements on left, and remaining on right
                  int nodesOnRight = numNodes - nodesOnLeft - 1;
                  trees[numNodes] += trees[nodesOnLeft] * trees[nodesOnRight];
                }
            }
            return trees[n];
        }
    }
    

Log in to reply
 

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