My Answer with C++ (28 lines)


  • 3
    N
    /**
     * 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;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.