All Possible Full Binary Trees LeetCode solution in C++

1
class Solution {
2
 public:
3
  unordered_map<int, vector<TreeNode *>> dp;
4
  int hash(int i, int j) {
5
    return (i * 21 + j);
6
  }
7
  vector<TreeNode *> fn(int l, int r) {
8
    int has = hash(l, r);
9
    if (dp.find(has) != dp.end()) {
10
      return dp[has];
11
    }
12
    vector<TreeNode *> res;
13
    if (r < l) {
14
      return {NULL};
15
    }
16
    if (r == l) {
17
      return {new TreeNode(0)};
18
    }
19
    for (int i = l + 1; i < r; i++) {
20
      vector<TreeNode *> left = fn(l, i - 1);
21
      vector<TreeNode *> right = fn(i + 1, r);
22
      for (auto le : left) {
23
        for (auto ri : right) {
24
          TreeNode *temp = new TreeNode(0);
25
          temp->left = le;
26
          temp->right = ri;
27
          res.push_back(temp);
28
        }
29
      }
30
    }
31
    return dp[has] = res;
32
  }
33
  vector<TreeNode *> allPossibleFBT(int n) {
34
    return fn(1, n);
35
  }