# Leetcode刷題學習筆記--Divide and Conquer
### [95. Unique Binary Search Trees II(Medium)](https://leetcode.com/problems/unique-binary-search-trees-ii/)
給定一個數字N，建立出所有1~N之間所有的unique BST。首先這題和[Unique Binary Search Tree](https://hackmd.io/474VEENxSVSGMRRRtfvetQ#96-Unique-Binary-Search-TreesMedium)類似，但是這題是要把全部的Tree建立出來。概念一樣，選定一個當root之後，分別建立出左右兩邊的BST(divide)，然後把左右兩邊的BST和root拼成一個新的BST(conquer)。

vector<TreeNode *> helper(int start, int end) {
    if(start > end) return {nullptr};
    if(start == end) return {new TreeNode(start)};
    vector<TreeNode *> rtn;
    for(int i = start; i <= end; ++i) {
        vector<TreeNode *> left = helper(start, i - 1);
        vector<TreeNode *> right = helper(i + 1, end);
        for(auto l : left)
            for(auto r : right)
                rtn.push_back(new TreeNode(i, l, r);
    }
        
    return rtn;
}
    
vector<TreeNode*> generateTrees(int n) {
    return helper(1, n);
}

###### tags: `leetcode` `刷題`