# A 0 ms c++ solution, with my explanation

• set `t[0]=1`; just for easy calculation.

`t[1]=1`, means when there is one node, return 1.

When n=2, {1,2}:

If '1' is root, there is 0 node left to build up left branch, and 1 node left to build up right branch. Thus when n=2, '1' is root, there are `t[0] * t[1]` trees.

If '2' is root, there is 1 node to build left branch, and 0 node to build right branch. Thus n=2, '2' is root, there are `t[1] * t[0]` trees.

So when n=2, there are `t[0]*t[1] + t[1]*t[0];` trees.

Use the 'root' to divide 1...n into two parts, then there are `t[remaining number of left] * t[remaining number of right]` trees for each 'root'.

``````int numTrees(int n)
{
vector<int> t(n + 1, 0);
t[0] = t[1] = 1;
int i, j;
for (i = 2; i <= n; ++i)
{
for (j = 1; j <= i / 2; ++j)
t[i] += t[j - 1] * t[i - j];
t[i] *= 2;
if (i % 2)
t[i] += t[i / 2] * t[i / 2];//Plus the middle 'root' trees.
}
return t[n];
}``````

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