6-line DP solution with explanation in C++


  • 0
    D

    This solution is similar to another top answer but with a different explanation which is based on the number of nodes on each subtrees.

    {Number of trees with n nodes} = {number of trees with 0 on left and n - 1 on right} + {number of trees with 1 on left and n - 2 on right} + ... + {number of trees with n - 1 on left and 0 on right}

    As total of nodes is n, putting i on left, 1 on root, then the right will be n - 1 - i.

    Therefore: f(n) = f(i) * f(n - 1 - i) for i = 0 to n - 1, where f(n) is the number of trees with n nodes. Number of trees with 0 nodes is 1

        int numTrees(int n) {
            vector<int> num_trees(n+1);
            num_trees[0] = 1;
            for (int i = 1; i <= n; ++i)
                for (int j = 0; j <= i - 1; ++j)
                    num_trees[i] += num_trees[j] * num_trees[i - 1 - j];
            return num_trees.back();
        }
    

Log in to reply
 

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