Share a C++ DP solution with O(1) space


  • 49
    W

    The basic idea is that we can construct the result of n node tree just from the result of n-1 node tree.
    Here's how we do it: only 2 conditions: 1) The nth node is the new root, so newroot->left = oldroot;

    1. the nth node is not root, we traverse the old tree, every time the node in the old tree has a right child, we can perform: old node->right = nth node, nth node ->left = right child; and when we reach the end of the tree, don't forget we can also add the nth node here.
      One thing to notice is that every time we push a TreeNode in our result, I push the clone version of the root, and I recover what I do to the old node immediately. This is because you may use the old tree for several times.
     class Solution {
        public:
            TreeNode* clone(TreeNode* root){
                if(root == nullptr)
                    return nullptr;
                TreeNode* newroot = new TreeNode(root->val);
                newroot->left = clone(root->left);
                newroot->right = clone(root->right);
                return newroot;
            }
            vector<TreeNode *> generateTrees(int n) {
                vector<TreeNode *> res(1,nullptr);
                for(int i = 1; i <= n; i++){
                    vector<TreeNode *> tmp;
                    for(int j = 0; j<res.size();j++){
                        TreeNode* oldroot = res[j];
                        TreeNode* root = new TreeNode(i);
                        TreeNode* target = clone(oldroot);
                        root->left = target;
                        tmp.push_back(root);
                       
                        if(oldroot!=nullptr){
                            TreeNode* tmpold = oldroot;
                            while(tmpold->right!=nullptr){
                                TreeNode* nonroot = new TreeNode(i);
                                TreeNode *tright = tmpold->right;
                                tmpold->right = nonroot;
                                nonroot->left = tright;
                                TreeNode *target = clone(oldroot);
                                tmp.push_back(target);
                                tmpold->right = tright;
                                tmpold = tmpold->right;
                            }
                            tmpold->right = new TreeNode(i);
                            TreeNode *target = clone(oldroot);
                            tmp.push_back(target);
                            tmpold->right = nullptr;
                        }
                    }
                    res=tmp;
                }
                return res;
            }
        };

  • 15
    D

    Great idea. I just make it more straightforward by two more functions.

    /**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    private:
        TreeNode * clone(TreeNode * root){
            if(NULL == root) return NULL;
            TreeNode * newRoot = new TreeNode(root->val);
            newRoot->left = clone(root->left);
            newRoot->right = clone(root->right);
            return newRoot;
        }
        void addToLeft(TreeNode * oldRoot, TreeNode * newRoot, vector<TreeNode *> & results){
            TreeNode * cloneRoot = clone(oldRoot);
            newRoot->left = cloneRoot;
            results.push_back(newRoot);
        }
        void addRight(TreeNode * oldRoot, TreeNode * cur, TreeNode * newNode, vector<TreeNode *> & results){
            TreeNode *cloneRoot = clone(oldRoot);
            TreeNode *newCur = cloneRoot;
            while(NULL != newCur){
                if(newCur->val == cur->val) break;
                else newCur = newCur->right;
            }
            assert(NULL != newCur);
            TreeNode * temp = newCur->right;
            newCur->right = newNode;
            newNode->left = temp;
            results.push_back(cloneRoot);
        }
    public:
        vector<TreeNode *> generateTrees(int n) {
            // DP:
            // for n-1 to n , for each n -1
            // 1) left to n
            // 2) for each right child down
            //    n replace right and right will be n left
            vector<TreeNode *> results;
            vector<TreeNode *> preResults(1, NULL);
            for(int i = 1; i <=n; i ++){
                for(int j = 0; j < preResults.size(); j++){
                    // add n-1 left to n 
                    TreeNode * oldRoot = preResults[j];
                    TreeNode * newRoot = new TreeNode(i);
                    addToLeft(oldRoot, newRoot, results);
                    TreeNode * cur = oldRoot;
                    while(NULL != cur){
                        TreeNode *newNode = new TreeNode(i);
                        addRight(oldRoot, cur, newNode, results);
                        cur = cur->right;
                    }
                }
                swap(results, preResults);
                results.clear();
            }
            return preResults;
        }
    };

  • 0
    W

    i have considered this way when solving the "Unique Binary Search Trees"


  • 0
    B

    Nice idea...


  • -13
    Y
    This post is deleted!

  • 0
    F
    This post is deleted!

  • 0
    J

    I don't think O(1) space claim is very accurate here...


  • 0
    S

    Great idea! I was thinking about using similar way, but found that it's hard to deal with i+1 when i + 1 can replace the root of a subtree. Now using your solution, it's similar to the problem "combination", in which we can clone the existing results, add new element to the cloned results, then put them all back! Also, the O(1) space is wrong...(1) For recursive clone, you need to keep at least one root-to-leaf path in the stack; (2) The temporary vector "tmp" will be the same size as the result.


  • 1
    X

    just another simpler version.

    class Solution {
    public:
    	TreeNode* clone(TreeNode* root){
    		if (root == NULL){
    			return NULL;
    		}
    		TreeNode* newroot = new TreeNode(root->val);
    		newroot->left = clone(root->left);
    		newroot->right = clone(root->right);
    		return newroot;
    	}
    	vector<TreeNode*> generateTrees(int n) {
    		vector<TreeNode*> ans(1, NULL);
    		for (int i = 1; i <= n; ++i){
    			vector<TreeNode*> tmp;
    			for (int j = 0; j < ans.size(); ++j){
    				TreeNode* newroot = new TreeNode(i);
    				TreeNode* oldroot = clone(ans[j]);
    				newroot->left = oldroot;
    				tmp.push_back(newroot);
    
    				TreeNode* p = oldroot;
    				while (p != NULL){
    					TreeNode* r = p->right;
    					TreeNode* newnode = new TreeNode(i);
    					p->right = newnode;
    					newnode->left = r;
    					tmp.push_back(clone(oldroot));
    					p->right = r;
    					p = p->right;
    				}
    			}
    			ans = tmp;
    		}
    		return ans;
    	}
    }
    

    ;


  • 3
    D

    @Wangxinlei
    I think, the TreeNode memory newed in while loop has not been freed


  • 0
    W

    Nice solution! I can see how the code works. However, I wonder how does this method guarantee that it can generate all of the unique BST. Can anyone provide the proof? Thanks a lot.


  • 0
    Q

    Simple and effective algorithm! Easy to be understood!


  • 0
    L

    @JieGhost It's somehow accurate because O(1) extra space are needed compared to the space of output


  • 0
    B

    I think your program has memory leakage problem. Can you have a look?


  • 1

    Great solution! I rewrite it in java.

        public List<TreeNode> generateTrees(int n) {
            List<TreeNode> result = new LinkedList<TreeNode>();
            if (n == 0) {
                return result;
            }
            result.add(null);
            for (int i = 1; i <= n; i++) {
                List<TreeNode> temp = new LinkedList<>();
                for (TreeNode node: result) {
                    TreeNode root = new TreeNode(i);
                    root.left = deepCopy(node);
                    temp.add(root);
                    
                    if (node == null) {
                        continue;
                    }
                    TreeNode transNode = node;
                    while (transNode.right != null) {
                        root = new TreeNode(i);
                        TreeNode cpNode = deepCopy(node);
                        TreeNode t = transNode.right;
                        transNode.right = root;
                        root.left = t;
                        TreeNode target = deepCopy(node);
                        temp.add(target);
                        transNode.right = t;
                        transNode = transNode.right;
                    }
                    root = new TreeNode(i);
                    transNode.right = root;
                    temp.add(deepCopy(node));
                    transNode.right = null;
                }
                result = new LinkedList<>(temp);
            }
            return result;
        }
        
        private TreeNode deepCopy(TreeNode root) {
            if (root == null) {
                return null;
            }
            TreeNode newRoot = new TreeNode(root.val);
            newRoot.left = deepCopy(root.left);
            newRoot.right = deepCopy(root.right);
            return newRoot;
        }
    

  • 0
    W

    Good solution, but it fails the n = 0 case. Adding the following would fix that though.

    if(!n) return {};
    

  • 1
    C

    Great job! And there is a non-memory-leak version.

    class Solution {
    public:
        vector<TreeNode*> generateTrees(int n) {
            return generateTrees_1(n);
        }
        
        TreeNode * clone(TreeNode *old_root)
        {
            if(old_root == NULL) return NULL;
            TreeNode *new_root = new TreeNode(old_root->val);
            new_root->left = clone(old_root->left);
            new_root->right = clone(old_root->right);
            
            return new_root;
        }
        
        vector<TreeNode*> generateTrees_1(int n)
        {
            if(n <= 0) return {};
            vector<TreeNode *> results;
            vector<TreeNode *> previous_result(1, NULL);
            for(int i = 1; i <= n; ++i)
            {
                for(int j = 0; j < previous_result.size(); ++j)
                {
                    // The nth node is the new root
                    TreeNode *new_root = new TreeNode(i);
                    TreeNode *new_left_subtree = clone(previous_result[j]);
                    new_root->left = new_left_subtree;
                    results.push_back(new_root);
                    
                    // traverse the old tree, use new node to replace the old right child
                    TreeNode *root = previous_result[j];
                    TreeNode *root_temp = root;
                    while(root_temp != NULL)
                    {
                        TreeNode *old_right_subtree = root_temp->right;
                        TreeNode *new_right_subtree = new TreeNode(i);
                        new_right_subtree->left = old_right_subtree;
                        root_temp->right = new_right_subtree;
                        TreeNode *new_tree = clone(root);
                        results.push_back(new_tree);
                        
                        root_temp->right = old_right_subtree;
                        delete new_right_subtree;
                        new_right_subtree = NULL;
                        root_temp = root_temp->right;
                    }
                }
                
                swap(results, previous_result);
                results.clear();
            }
                  
            return previous_result;
        }
    };
    

Log in to reply
 

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