When the number of nodes is 1 there is just one possible tree- this is the base case
Consider that every node can be the root - the nodes before it will be on the left and the nodes after it on the right
3.程式碼
class Solution {
public:
int numTrees(int n) {
vector<int> v(n + 1, -1);
return numTreesCount(n, v);
}
private:
int numTreesCount(int n, vector<int>& v) {
if (n == 0 || n == 1) {
return 1;
}
if (v[n] != -1) {
return v[n];
}
int sum = 0;
for (int i = 1; i <= n; i++) {
int left = numTreesCount(i - 1, v);
int right = numTreesCount(n - i, v);
sum = sum + left * right;
}
v[n] = sum;
return sum;
}
};
