Share my DP C++ solution,beats 91.82%,easy understand


  • 2
    C
    void genTree(TreeNode* root, TreeNode* left, TreeNode* right,int &num){
        if(left){
            root->left = new TreeNode(left->val);
            genTree(root->left,left->left,left->right,num);
        }
        root->val = ++ num;
        if(right){
            root->right = new TreeNode(right->val);
            genTree(root->right,right->left,right->right,num);
        }
    }
    vector<TreeNode*> generateTrees(int n) {
        vector<vector<TreeNode*> > res(n + 1);
        if(!n) return res[0];
        res[0] = {NULL};
        res[1] = {new TreeNode(1)};
        for(int i = 2;i <= n; ++ i){
            for(int j = 1;j <= i; ++ j){
                for(int x = 0; x < res[j - 1].size(); ++ x)
                    for(int y = 0; y < res[i - j].size(); ++ y)
                    {
                        int num = 0;
                        TreeNode *tmp = new TreeNode(j);
                        genTree(tmp,res[j - 1][x],res[i - j][y],num);
                        res[i].push_back(tmp);
                    }
            }
        }
        return res[n];
    }

  • 0
    R

    your code is excellent but you should explain it . thank you


Log in to reply
 

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