C++ divide and conquer


  • 0
    J
    /**
     * 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*> generateTrees(int n) {
            vector<TreeNode*> ans;
            if(n==0) return ans;
            return dfs(1,n);    
        }
        vector<TreeNode*> dfs(int start,int end)
        {
            vector<TreeNode*> ans;
            if(start>end) {ans.push_back(NULL);return ans;}
            if(start == end) {TreeNode *root = new TreeNode(start); ans.push_back(root);return ans;}
            for(int i = start;i<=end;i++)
            {  
                auto left = dfs(start,i-1);
                auto right = dfs(i+1,end);
                for(auto l:left)
                    for(auto r:right)
                    {
                        TreeNode *root = new TreeNode(i);
                        root->left = l;
                        root->right = r;
                        ans.push_back(root);
                    }
            }
            return ans;
        }
    };
    

Log in to reply
 

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