My c++ novelty idea ,28ms。use DP


  • 0
    S

    The basic idea is we can get the result of n node tree form result of 0 node tree to n-1 node tree.
    We use dp[i] to save the result of i node tree.
    Given a sequence 1…i, we pick a number j out of the sequence as the root.
    then, root->left = dp[j - 1]; root->right = dp[i - j] +j

    My english is not good , so , read the code.
    By the way , the code may cause memory leak.

    class Solution {
    public:
        vector<TreeNode*> generateTrees(int n) {
            vector<vector<TreeNode*>> dp(n + 1);
            if (n < 1) {
                dp[0].push_back(NULL);
                return dp[0];
            }
            dp[0].push_back(NULL); dp[1].push_back(new TreeNode(1));
            for (int i = 2; i < n + 1; i++) {
                for (int j = 1; j <= i; j++)
                    for (int k = 0; k < dp[j - 1].size(); k++)
                        for (int w = 0; w < dp[i-j].size(); w++)
                        {
                            dp[i].push_back(new TreeNode(j));
                            dp[i].back()->left = dp[j-1][k];                   
                            traverse_add_copy(dp[i - j][w], &dp[i].back()->right, j);
                        }
            }
            return dp[n];
        }
    private:
        void traverse_add_copy(TreeNode* root, TreeNode **dst, int val)
        {
            if (root == NULL) return;
            *dst = new TreeNode(root->val + val);
            if (root->left)
                traverse_add_copy(root->left, &(*dst)->left, val);
            if (root->right)
                traverse_add_copy(root->right, &(*dst)->right, val);
        }
    };

Log in to reply
 

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