A very concise C++ top-down dynamic programming solution


  • 0
    L
    class Solution {
    public:
        vector<vector<vector<TreeNode *>>> dp;
        vector<TreeNode *> dfs(int l, int r, vector<vector<vector<TreeNode *>>> &dp) {
            if (l > r)
                return vector<TreeNode *>(1, NULL);
            if (!dp[l - 1][r - 1].empty())
                return dp[l - 1][r - 1];
            for (int i = l; i <= r; ++i) {
                auto left = dfs(l, i - 1, dp);
                auto right = dfs(i + 1, r, dp);
                for (auto lc : left)
                    for (auto rc : right) {
                        TreeNode *root = new TreeNode(i);
                        root->left = lc;
                        root->right = rc;
                        dp[l - 1][r - 1].push_back(root);
                    }
            }
            return dp[l - 1][r - 1];
        }
        vector<TreeNode*> generateTrees(int n) {
            if (n <= 0)
                return vector<TreeNode *>();
            dp.resize(n, vector<vector<TreeNode *>>(n));
            return dfs(1, n, dp);
        }
    };

Log in to reply
 

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