LeetCode 95. Unique Binary Search Trees II [Medium] [C++] 解題筆記

這題給我們一個數字 n 要我們列舉出所有 1 ... n 的數可以形成的 unique binary search tree.

EX:

      Input: 3

      Output:
    [
      [1,null,3,2],
      [3,2,null,1],
      [3,1,null,null,2],
      [2,1,3],
      [1,null,2,null,3]
    ]
  Explanation:
  The above output corresponds to the 5 unique BST's shown below:

   1         3     3      2      1
    \         /     /        / \      \
     3     2     1      1   3      2
    /       /       \                    \
   2     1         2                   3

想法:

        這題是 96. Unique Binary Search Trees 的進階題，96 題只需要求出個數，因此可以套用卡特蘭數的

公式或是找出遞迴式用DP求解，但這題需要列出 BST 具體的結構，就必須使用 recursive 的方式一一列舉，

複雜度就是 n 階卡特蘭數，概念上與 96 題有點類似，就是將每個 node i 都當成 root 然後在分別去列舉它的

左右子樹可以形成的 BST 然後再列舉每個左子樹與每個右子樹加上 i 作為 root 形成的 BST ，有點 divide and conquer 的味道。

完整程式碼:

 
class Solution {
public:
    vector<TreeNode*> generate_bst(int s, int e) {
        vector<TreeNode*> bst;
        if (s > e) { 
            bst.emplace_back(nullptr);
            return bst;
        }
        else if (s == e) {
            bst.emplace_back(new TreeNode(s));
            return bst;
        }
        vector<TreeNode*> left, right;
        for (int i = s; i <= e; i++) {
            left = generate_bst(s, i - 1);
            right = generate_bst(i + 1, e);
            for (auto left_subtree : left) {
                for (auto right_subtree : right) {
                    auto root = new TreeNode(i);
                    root->left = left_subtree;
                    root->right = right_subtree;
                    bst.emplace_back(root);
                }
            }
        }
        return bst;
    }
    vector<TreeNode*> generateTrees(int n) {
        if (n == 0) { 
            return {};
        }
        return generate_bst(1, n);
    }
};