# C++ code w/ explanation

• 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}

• You are such a talent! What a cool solution!

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