Today I have done leetcode's August LeetCoding Challenge with cpp.

August LeetCoding Challenge 5

Description

Unique Binary Search Trees II

Given an integer n, return all the structurally unique BST's (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.

Example 1:

Input: n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

Example 2:

Input: n = 1
Output: [[1]]

Constraints:

• 1 <= n <= 8

Solution

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();
TreeNode *copy(TreeNode *root) {
  if(!root) return nullptr;
  return new TreeNode(root->val, copy(root->left), copy(root->right));
}
class Solution {
  vector<TreeNode*> solve(int mask) {
    if(!mask) return {nullptr};
    vector<TreeNode*> answer;
    for(int i = 0; i < 8; ++i) {
      if(!(mask & (1 << i))) continue;
      auto left = solve(mask & ((1 << i) - 1));
      auto right = solve(mask & (((1 << 8) - 1) ^ ((1 << (i + 1)) - 1)));
      for(auto l : left) {
        for(auto r : right) {
          answer.push_back(new TreeNode(i + 1, copy(l), copy(r)));
        }
      }
    }
    return answer;
  }
public:
  vector<TreeNode*> generateTrees(int n) {
    return solve((1 << n) - 1);
  }
};

// Accepted
// 8/8 cases passed (20 ms)
// Your runtime beats 51.27 % of cpp submissions
// Your memory usage beats 6.95 % of cpp submissions (19.7 MB)