Simple C++ Solution (Beats 96+%)


  • 0
    W

    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);
        }
    };
    

Log in to reply
 

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