# Simple C++ Solution (Beats 96+%)

• share my "get and calculate" DP simple c++ solution. (I have used this get-calculate model in many problems and it worked well).

class Solution {
private:
map<pair<int, int>, vector<TreeNode*>*> storage;
void calculateTrees(pair<int, int> beginEnd) {
int begin = beginEnd.first;
int end = beginEnd.second;
vector<TreeNode*> *res = new vector<TreeNode*>;
if (end < begin) {
res->push_back(NULL);
} else {
for (int rootValue = begin; rootValue <= end; ++rootValue) {
pair<int, int> leftKey(begin, rootValue - 1);
pair<int, int> rightKey(rootValue + 1, end);
vector<TreeNode*> *leftTrees = getTrees(leftKey);
vector<TreeNode*> *rightTrees = getTrees(rightKey);
for (auto lit = leftTrees->begin(); lit != leftTrees->end(); ++lit) {
for (auto rit = rightTrees->begin(); rit != rightTrees->end(); ++rit) {
TreeNode *rootNode = new TreeNode(rootValue);
rootNode->left = *lit;
rootNode->right = *rit;
res->push_back(rootNode);
}
}
}
}
storage[beginEnd] = res;
}
vector<TreeNode*> *getTrees(pair<int, int> beginEnd) {
if (storage.find(beginEnd) == storage.end()) {
calculateTrees(beginEnd);
}
return storage[beginEnd];
}
vector<TreeNode*> *generateTrees(int begin, int end) {
pair<int, int> beginEnd(begin, end);
return getTrees(beginEnd);
}
public:
vector<TreeNode*> generateTrees(int n) {
if (n == 0)
return vector<TreeNode*>();
return *generateTrees(1, n);
}
};

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