95. Unique Binary Search Trees II - cocoder39/coco39_LC GitHub Wiki

95. Unique Binary Search Trees II

Main idea is same as 96. Unique Binary Search Trees , here we divide and conquer the problem by taking advantage of Tree structure.

Supposing the time complexity of building a bst with n nodes is T(n), then T(n) = sum(T(i)*T(n - 1- i)) where 0 <= i <= n, which is exactly the recursive formula of catalan number. Thus T(n) = O(Catalan(n)).

class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if (n == 0) {
            return {};
        }
        return helper(1, n);
    }
private:
    vector<TreeNode*> helper(int start, int end) {
        vector<TreeNode*> res;
        if (start > end) {
            res.push_back(nullptr);
            return res;
        }
        
        for (int i = start; i <= end; i++) {
            vector<TreeNode*> lefts = helper(start, i - 1);
            vector<TreeNode*> rights = helper(i + 1, end);
            for (auto left : lefts) {
                for (auto right : rights) {
                    TreeNode* root = new TreeNode(i);
                    root->left = left;
                    root->right = right;
                    res.push_back(root);
                }
            }
        }
        return res;
    }
};

One point is that the helper() function can either return vector<TreeNode*> or pass vector<TreeNode*> as an argument, returns TreeNode* makes it complicated. Given left and right bounds, a bunch of unique BSTs will be generated rather than only one BST

⚠️ **GitHub.com Fallback** ⚠️