30 ms c++ solution


  • 16
    P
    /**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        vector<TreeNode *> generateTrees(int n) {
            return helper(1,n);
        }
        
        vector<TreeNode*> helper(int s, int e) {
            if (s > e) {
                 return vector<TreeNode*>(1,NULL);
            }
            
            vector<TreeNode*> result;
            for (int i=s; i <= e; ++i) {
                vector<TreeNode*> left, right;
                    left = helper(s,i-1);
                    right = helper(i+1,e);
                    for (int j = 0; j < left.size(); ++j) {
                        for (int k = 0; k < right.size(); ++k) {
                            TreeNode* root = new TreeNode(i);
                            root->left = left[j];
                            root->right = right[k];
                            result.push_back(root);
                        }
                    }
            }
            
            return result;
        }
    };

  • 1
    K

    Always find recursion tricky for me, just can't get the meaning of this code


  • -1
    R
    This post is deleted!

  • 0
    R

    what is the space and time complexity?>


  • 0
    W

    Nice and easy understand, thank you.


  • 0
    F

    I can only understand others' recursive code by list recursion nodes, it is hard to write by myself


  • 0
    N

    how do you free up space for the new root nodes?

    And why you have to create the run this line below in the inner most loop each time, rather than one time per i?

    TreeNode* root = new TreeNode(i);

Log in to reply
 

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