construct n from n-1


  • 0
    Z
    class Solution {
    private:
        TreeNode* copyTree(TreeNode* root)
        {
            if(root == NULL) return NULL;
            TreeNode* res = new TreeNode(root->val);
            if(root->left != NULL) res->left = copyTree(root->left);
            if(root->right != NULL) res->right = copyTree(root->right);
            return res;
        }
    public:
        vector<TreeNode*> generateTrees(int n) {
            vector<TreeNode*> res;
            if(n <= 0) return res;
            TreeNode* one = new TreeNode(1);
            res.push_back(one);
            for(int i=2;i<=n;++i)
            {
                vector<TreeNode*> tmp = res;
                int size = res.size();
                // as root 
                for(int j=0;j<size;++j)
                {
                    TreeNode* root = new TreeNode(i);
                    root->left = copyTree(tmp[j]);
                    res[j] = root;
                }
                // as right son
                for(int j=0;j<size;++j)
                {
                    int level = 0;
                    TreeNode* rt = tmp[j];
                    while(rt != NULL)
                    {
                        int count = 0;
                        TreeNode* copy = copyTree(tmp[j]);
                        TreeNode* p = copy;
                        while(count != level) {p = p->right; ++count;}
                        TreeNode* ii = new TreeNode(i);
                        ii->left = p->right;
                        p->right = ii;
                        
                        rt = rt->right;
                        ++level;
                        res.push_back(copy);
                    }
                }
            }
            return res;
        }
    };

Log in to reply
 

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