C++ code w/ explanation


  • 18
    G
    class Solution {
    public:
        int numTrees(int n) {
            vector<int> f;
            f.push_back(1);
            for (int i = 1; i <= n; ++i) {
                int t = 0;
                for (int j = 0; j < i; ++j)
                    t += f[j] * f[i-j-1];
                f.push_back(t);
            }
            return f.back();
        }
    };
    

    Consider f_i:

    • choose 1 as the root, we have 0 node for the left tree, i-1 for the
      right;
    • choose 2 as the root, we have 1 node for the left tree, i-2 for the
      right;
    • ...
    • choose i as the root, we have i-1 nodes for the left tree, 0 for the
      right.

    Therefore, the recursive solution is f_i = \sum_{j=0}^{i-1} f_j f_{i-j-1}


  • 0
    L

    You are such a talent! What a cool solution!


Log in to reply
 

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