A concise recursive solution


  • 0
    S
    vector<TreeNode *> generateTrees(int n) {
        vector<TreeNode *> ans = getRoot(1, n);
        return ans;
    }
    
    vector<TreeNode *> getRoot(int s, int e) {
        vector<TreeNode *> ans;
        TreeNode *root = NULL;
        
        if (s >= e) {
            root = (s == e) ? new TreeNode(s) : NULL;  
            ans.push_back(root);
            return ans;
        }
        
        for(int i = s; i<= e; ++i) {
            vector<TreeNode *> leftSet;
            vector<TreeNode *> rightSet;
            leftSet = getRoot(s, i - 1);
            rightSet = getRoot(i + 1, e);
            
            for (int j = 0; j < leftSet.size(); ++j) {
                for (int k = 0; k < rightSet.size(); ++k) {
                    root = new TreeNode(i);
                    root->left = leftSet[j];
                    root->right = rightSet[k];
                    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.