Share my C++ Divide and Conquer solution


  • 0
    X
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        vector<TreeNode*> helper(int start, int end){
            vector<TreeNode*> allTrees;
            if(start>end||end<start||start==end){
                TreeNode* root=NULL;
                if(start==end)
                    root=new TreeNode(start);
                allTrees.push_back(root);
                return allTrees;
            }        
    
            for(int i=start; i<=end; i++){
                vector<TreeNode*> ltrees=helper(start, i-1);
                vector<TreeNode*> rtrees=helper(i+1, end);
                
                for(int l=0; l<ltrees.size(); ++l){
                    for(int r=0; r<rtrees.size(); ++r){
                        TreeNode* root=new TreeNode(i);
                        root->left=ltrees[l];
                        root->right=rtrees[r];
                        allTrees.push_back(root);
                    }
                }
            }
            
            return allTrees;
        }
        
        vector<TreeNode*> generateTrees(int n) {
            vector<TreeNode*> allTrees;
            int start=1;
            int end=n;
            for(int i=1; i<=n; i++){
                vector<TreeNode*> ltrees=helper(start, i-1);
                vector<TreeNode*> rtrees=helper(i+1, end);
                
                for(int l=0; l<ltrees.size(); ++l){
                    for(int r=0; r<rtrees.size(); ++r){
                        TreeNode* root=new TreeNode(i);
                        root->left=ltrees[l];
                        root->right=rtrees[r];
                        allTrees.push_back(root);
                    }
                }
            }
            return allTrees;
        }
    };

Log in to reply
 

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