My non-recursive C++ solution


  • 5
    R
    vector<TreeNode *> generateTrees(int n) {
        vector<TreeNode *> tmp;
        vector<TreeNode *> ret;
        tmp.push_back(NULL);        
        ret.push_back(new TreeNode(1));
        if (!n) return tmp;
    
    	/* insert the largeset number into previously contructed trees */
        for (int i = 2; i <= n; i++) {
            tmp.clear();
            for (int j = 0; j < ret.size(); j++) {
    			/* firstly, put the largest number on the top of tree */
                TreeNode *orgTree = ret[j];                
                TreeNode *newNode = new TreeNode(i);
                newNode->left = copy(orgTree);
                tmp.push_back(newNode);
                
    			/* traverse thru the right-most branch, 
    			 * insert the largest number one position after another */
                TreeNode *orgRunner = orgTree;
                while (orgRunner) {
                    newNode = new TreeNode(i);
                    newNode->left = orgRunner->right;
                    orgRunner->right = newNode;
                    tmp.push_back(copy(orgTree));
    				
    				/* recover the original tree */
                    orgRunner->right = orgRunner->right->left;
    				
    				/* for the next loop */
                    orgRunner = orgRunner->right;
                }
            }
            ret =  tmp;
        }
        return ret;
    }
    
    TreeNode *copy (TreeNode *root) {
        TreeNode *ret = NULL;
        if (root) {
            ret = new TreeNode(root->val);
            ret->left = copy(root->left);
            ret->right = copy(root->right);
        }
        return ret;
    }

Log in to reply
 

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