18 ms c++ recursive solution


  • 12
    P
    vector<vector<int> > pathSum(TreeNode *root, int sum) {
            vector<vector<int> > result;
            vector<int> cur_path(0);
            pathSumRec(root, sum, result, cur_path);
            return result;
        }
        
        // pass the current path as a reference and remember to pop out the last added element
        // this improves the performance by 5 times
        void pathSumRec(TreeNode* root, int sum, vector<vector<int> >& result, vector<int>& cur_path) {
            if (root == NULL) {
                return;
            }
            
            if (root->val == sum && root->left == NULL && root->right == NULL) {
                cur_path.push_back(root->val);
                result.push_back(cur_path);
                cur_path.pop_back();
                return;
            }
            
            int sum_left = sum - root->val;
            cur_path.push_back(root->val);
            pathSumRec(root->left, sum_left, result, cur_path);
            //cur_path.pop_back();
            pathSumRec(root->right, sum_left, result, cur_path);
            cur_path.pop_back();
        }

  • 0
    J

    any explanation?

    i can't understand what does the "pop_back()" do


  • 0
    P

    pop_back removes the last added element from the vector.


  • 0
    Z

    you are right, it will improve the performance by 4 tmes.


  • 0
    L

    if you don't "pop_back( )", the wrong answer will remain in the vector<int>.
    Note that all the recursions are using the same vector<int>. So, if the sum isn't right, you have to "pop_back( )".
    Even the answer is right, you have to "pop_back" because there may be another right answer.


  • 0
    J

    thank you for your explanation!


  • 0
    L

    why will popping out the last added element improve the performance? any explanations?


  • 0
    L

    I commented out the code to pop out, it failed the tests.


Log in to reply
 

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