Leetcode刷題學習筆記–Divide and Conquer

95. Unique Binary Search Trees II(Medium)

給定一個數字N，建立出所有1~N之間所有的unique BST。首先這題和Unique Binary Search Tree類似，但是這題是要把全部的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 刷題
Select a repo