My C++ 20ms solution using DP


  • 1
    M
    class Solution {
    public:
        vector<TreeNode*> generateTrees(int n) {
            vector<TreeNode*> trees(1, nullptr);
            for (int i = 1; i <= n; i++) {
                int len = trees.size();
                for (int j = 0; j < len; j++) {
                    TreeNode *root = trees[j];
                    TreeNode *it = root;
                    while (it != nullptr) {
                        TreeNode node(i);
                        node.left = it->right;
                        it->right = &node;
                        TreeNode *root_copy = cloneTree(root);
                        trees.push_back(root_copy);
                        it->right = it->right->left;
                        it = it->right;
                    }
                    TreeNode *node = new TreeNode(i);
                    node->left = root;
                    trees[j] = node;
                }
            }
            return trees;
        }
    private:
        TreeNode* cloneTree(TreeNode *root) {
            if (root == nullptr) {
                return nullptr;
            }
            TreeNode *root_copy = new TreeNode(root->val);
            root_copy->left = cloneTree(root->left);
            root_copy->right = cloneTree(root->right);
            return root_copy;
        }
    };

Log in to reply
 

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