I think most of answer is wrong in discuss


  • 1
    S

    This is the answer of my first time submission

    class Solution {
    public:
        vector<TreeNode*> getNode(int left, int right) {
            vector<TreeNode*> res{NULL};
            if (left <= right) {
                res.pop_back();
                for (int i = left; i <= right; i++) {
                    vector<TreeNode*> l = getNode(left, i - 1);
                    vector<TreeNode*> r = getNode(i + 1, right);
                    for (auto ll : l) {
                        for (auto rr : r) {
                            TreeNode* node = new TreeNode(i);
                            node -> left = ll;
                            node -> right = rr;
                            res.push_back(node);
                        }
                    }
                }
            }
            return res;
        }
        vector<TreeNode*> generateTrees(int n) {
            return getNode(1, n);
        }
    };
    

    But after deep thought, I find this code may lead to a lot of memory leaks, and trees are not deep copy.
    So I add two more steps in the solution.

    class Solution {
    public:
        TreeNode* copyTreeNode(TreeNode* root) {
            if (!root) return root;
            TreeNode* newRoot = new TreeNode(root -> val);
            newRoot -> left = copyTreeNode(root -> left);
            newRoot -> right = copyTreeNode(root -> right);
            return newRoot;
        }
        void removeTreeNode(TreeNode* root) {
            if (!root) return;
            TreeNode* left = root -> left;
            TreeNode* right = root -> right;
            delete root;
            root = NULL;
            removeTreeNode(left);
            removeTreeNode(right);
        }
        vector<TreeNode*> getNode(int left, int right) {
            vector<TreeNode*> res{NULL};
            if (left <= right) {
                res.pop_back();
                for (int i = left; i <= right; i++) {
                    vector<TreeNode*> l = getNode(left, i - 1);
                    vector<TreeNode*> r = getNode(i + 1, right);
                    for (auto ll : l) {
                        for (auto rr : r) {
                            TreeNode* node = new TreeNode(i);
                            node -> left = copyTreeNode(ll);
                            node -> right = copyTreeNode(rr);
                            res.push_back(node);
                        }
                    }
                    for (auto x : l) {
                        removeTreeNode(x);
                    }
                    for (auto x : r) {
                        removeTreeNode(x);
                    }
                }
            }
            return res;
        }
        vector<TreeNode*> generateTrees(int n) {
            return getNode(1, n);
        }
    };
    

    Please let me know if I`m wrong.


Log in to reply
 

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