LC95 Unique Binary Search Trees

本题链接：Unique Binary Search Trees II

本题标签：Tree, Dynamic Programming

本题难度：

方案1：

class Solution {
private:
    vector<TreeNode*> genTrees(int begin, int end)
    {
        vector<TreeNode*> temp;
        if(begin > end)
            temp.push_back(NULL);
        else if(begin == end)
            temp.push_back(new TreeNode(begin));
        else
        {
            for(int i = begin; i <= end; ++i)
            {
                vector<TreeNode*> left = genTrees(begin, i - 1);
                vector<TreeNode*> right = genTrees(i + 1, end);
                
                for(int j = 0; j < left.size(); ++j)
                {
                    for(int k = 0; k < right.size(); ++k)
                    {
                        TreeNode* root = new TreeNode(i);
                        root->left = left[j];
                        root->right = right[k];
                        temp.push_back(root);
                    }
                }
            }
        }
        return temp;
    }
    
public:
    vector<TreeNode*> generateTrees(int n) {
        if(n < 1)
            return vector<TreeNode*>();
        
        return genTrees(1, n);
    }
};

时间复杂度：

空间复杂度：