95

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        return generate(1, n);
    }

    vector<TreeNode*> generate(int left, int right){
        vector<TreeNode*> ans;
        // Condition of child of leaf node.
        if(left > right){
            ans.push_back(NULL);
            return ans;
        }

        // Consider each point as root and recursively generate trees.
        for(int i=left; i<=right; i++){
            auto leftTrees = generate(left, i-1);
            auto rightTrees = generate(i+1, right);
            for(auto l: leftTrees){
                for(auto r: rightTrees){
                    TreeNode *node = new TreeNode(i);
                    node->left = l;
                    node->right = r;
                    ans.push_back(node);
                }
            }
        }
        return ans;
    }
};

---------------------------

class Solution {
public:
  map <pair<int, int>, vector<TreeNode*>> cache;
  vector<TreeNode*> generateTreesR(int start, int end) {
    if (cache.find({start, end}) != cache.end())
      return cache[{start, end}];

    vector<TreeNode*> res;
    if (start > end) {
      res.push_back(NULL);
      cache[{start, end}] = res;
      return res;
    }

    if (start == end) {
      TreeNode* head = new TreeNode(start);
      res.push_back(head);
      cache[{start, end}] = res;
      return res;
    }

    for (int i=start; i<=end; i++) {
      // Make ith as root node.
      vector<TreeNode*> res_left = generateTreesR(start, i-1);
      vector<TreeNode*> res_right = generateTreesR(i+1, end);
      for (auto left_tree: res_left) {
        for (auto right_tree: res_right) {
          TreeNode* head = new TreeNode(i);
          head->left = left_tree;
          head->right = right_tree;
          res.push_back(head);
        }
      }
    }

    cache[{start, end}] = res;
    return res;
  }

  vector<TreeNode*> generateTrees(int n) {
    return generateTreesR(1, n);
  }
};