Short and simple java solution with intuitive explanation


  • 3
    A

    arr stores the number of trees that can be formed for number of nodes i = 0, 1, 2, 3 .. n. To be able to fill a[i] ie. the number of trees that can be formed with i nodes, we need to consider the number of nodes in the left subtree which can be from 0 to i-1 (1 node is needed for the root) , lets call the number of nodes in the left subtree j. Thus, the right subtree will have i - 1 - j nodes. Putting all this together, the number of trees with i nodes will be the sum of arr[j] * arr[i-1-j] for j = 0 to i-1.

    public int numTrees(int n) {
        int[] arr = new int[n+1];
        arr[0] = 1;
    
        for (int i=1; i<=n; i++) {
            int count = 0;
            
            for (int j=0; j<i; j++) {
                int left = j;
                int right = i-1-j;
                count += arr[left] * arr[right];                
            }
            
            arr[i] = count;
        }
        
        return arr[n];
    }

Log in to reply
 

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