C++ recursive solution, easy to understand


  • 0
    B

    for root at i, the unique BST has left child as all unique BST between 1 to i-1, has right child as all unique BST between i+1 to n. And the overall results have root traverse from 1 to n. So this intuitively lead to a recursive solution.

    The help function is used to generate all combination of unique BST in a given range

    class Solution {
    public:
        vector<TreeNode*> generateTrees(int n) 
        {
            vector<TreeNode*> ans;
            if(n<1) return ans;
            for(int i = 1; i <= n; i++)
            {
                vector<TreeNode*> left = help(1,i-1);
                vector<TreeNode*> right = help(i+1,n);
                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;
        }
        
        vector<TreeNode*> help(int start, int end) 
        {
            vector<TreeNode*> ans;
            if(start>end)
            {
                ans.push_back(NULL);
                return ans;
            }
            for(int i = start; i<= end; i++)
            {
                vector<TreeNode*> left = help(start,i-1);
                vector<TreeNode*> right = help(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.