Clean C++ implementation


  • 1

    I referred to the top voted solution, I THINK THIS THE PATTERN

         left = help(...)
         right = help(...) 
         for ( all : left ) 
               for( all : right)
                       combine
    

    Code:

    class Solution {
    public:
        vector<TreeNode*> generateTrees(int n) {
            vector<TreeNode*> result;
            if(n==0)  return result;
            return help(1, n);
        }
        
        vector<TreeNode*> help(int s, int e){
            if(s>e)   return vector<TreeNode*>(1, NULL);
            vector<TreeNode*> result;
            for(int i=s; i<=e; i++){
                vector<TreeNode*> left, right;
                left=help(s, i-1);
                right=help(i+1, e);
                for(int m=0; m<left.size(); m++){
                    for(int n=0; n<right.size(); n++){
                        TreeNode* root=new TreeNode(i);
                        root->left=left[m];
                        root->right=right[n];
                        result.push_back(root);
                    }
                }
            }
            return result;
        }
    };

  • 0
    2
    class Solution {
    public:
        vector<TreeNode*> generateTrees(int n) {
            vector<TreeNode*> result;
            if(n == 0)  return result;
            
            return help(1, n);
        }
        
        vector<TreeNode*> help(int start, int end) {
            if(start == end)  return { new TreeNode(start) };
            if(start > end)  return { nullptr };
            
            vector<TreeNode*> result;
            for(int i = start; i <= end; i ++) {
                vector<TreeNode*> lefts = help(start, i-1);
                vector<TreeNode*> rights = help(i+1, end);
                for(auto left : lefts) {
                    for(auto right : rights) {
                        TreeNode* root = new TreeNode(i);
                        root->left = left;
                        root->right = right;
                        result.push_back(root);
                    }
                }
            }
            return result;
        }
    };

Log in to reply
 

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