Unique Binary Search Trees II

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int *f;
    TreeNode* generateTree(int rank, int base, int n) {
        if (n == 0) return NULL;
        if (n == 1) return new TreeNode(base);
        for (int i = 0; i < n; ++i) {
            rank -= f[i] * f[n - 1 - i];
            if (rank < 0) {
                TreeNode* root = new TreeNode(base + i);
                rank += f[i] * f[n - 1 - i];
                root->left = generateTree(rank % f[i], base, i);
                root->right = generateTree(rank / f[i], base + i + 1, n - 1 - i);
                return root;
            }
        }
    }
    vector<TreeNode *> generateTrees(int n) {
        f = new int[n + 1];
        f[0] = f[1] = 1;
        for (int i = 2; i <= n; ++i) {
            f[i] = 0;
            for (int j = 0; j < i; ++j) f[i] += f[j] * f[i - 1 - j];
        }
        vector<TreeNode *> result;
        for (int i = 0; i < f[n]; ++i) result.push_back(generateTree(i, 1, n));
        return result;
    }
};