#include <vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// generate trees for range [n, m]
vector<TreeNode *> generateTrees(int m, int n) {
    if (n < m) return vector<TreeNode *>(1);

    // we can use 2-dimension array to cache the result, but since the test
    // case is very small, but result is very large, so no cache so far

    vector<TreeNode *> result;

    for (int i = m; i <= n; ++i) {
        vector<TreeNode *> leftChildren = generateTrees(m, i-1);
        vector<TreeNode *> rightChildren = generateTrees(i+1, n);

        size_t leftSize = leftChildren.size();
        size_t rightSize = rightChildren.size();

        for (size_t left = 0; left < leftSize; ++left) {
            for (int right = 0; right < rightSize; ++right) {
                TreeNode * r = new TreeNode(i);

                // here require **deep copy** for left/right children
                // but it would still pass test
                r->left = leftChildren[left];
                r->right = rightChildren[right];
                result.push_back(r);
            }
        }
    }

    return result;
}


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