12ms 11-lines C++ Solution


  • 45

    Well, a typical backtracking problem. The code is as follows. You may walk through it using the example in the problem statement to see how it works.

    class Solution {
    public:
        vector<vector<int>> pathSum(TreeNode* root, int sum) {
            vector<vector<int> > paths;
            vector<int> path;
            findPaths(root, sum, path, paths);
            return paths;  
        }
    private:
        void findPaths(TreeNode* node, int sum, vector<int>& path, vector<vector<int> >& paths) {
            if (!node) return;
            path.push_back(node -> val);
            if (!(node -> left) && !(node -> right) && sum == node -> val)
                paths.push_back(path);
            findPaths(node -> left, sum - node -> val, path, paths);
            findPaths(node -> right, sum - node -> val, path, paths);
            path.pop_back();
        }
    };

  • 0
    L
    This post is deleted!

  • 2
    Y

    I tested your codes, but the running time is not 12ms, but 16ms. I don't know why.


  • 0

    Hi, YuzeJin. It's Ok. The same piece of code may also have some time variances at different times. The world is just not that accurate :-)


  • 0
    J

    Is there an iterative solution, jianchao? I have tried, but I find it is difficult to keep track of the path sum.


  • 0

    Hi, @jin23. I guess for such backtracking-style problems, an iterative solution is somewhat difficult. Yeah, like you mention, it will be difficult to keep track of the necessary information.


  • 2
    C

    Hi, I have a iterative solution which cost 16ms, the main idea is to use a stack to store the current path, by traversing the tree to find all possible paths to leaf nodes, one's able to get all possible paths that satisfy the sum, maybe you will be interested to take a look:

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        vector<vector<int>> pathSum(TreeNode* root, int sum) {
            int psum = 0;
            vector<TreeNode*> path;
            vector<vector<int>> result;
            
            if (!root) return result;
            
            psum += root->val;
            path.push_back(root);
            
            TreeNode* cur;
            TreeNode* pop = root;
            
            while(!path.empty()) {
                cur = path.back();
                if (psum == sum && cur->left == NULL && cur->right == NULL) {
                    vector<int> pathResult;
                    for(int i = 0; i < path.size(); i++) {
                        pathResult.push_back(path[i]->val);
                    }
                    result.push_back(pathResult);
                    
                }
                
                if ((cur->left == NULL && cur->right == NULL) || (cur->right == pop) || (cur->left == pop && cur->right == NULL)) {
                    pop = cur;
                    psum -= cur->val;
                    path.pop_back();
                }
                
                else if (cur->left == NULL || cur->left == pop) {
                    cur = cur->right;
                    path.push_back(cur);
                    psum += cur->val;
                }
                
                else {
                    cur = cur->left;
                    path.push_back(cur);
                    psum += cur->val;
                }
                
            }
            
            return result;
        }
    };

  • 3
    class Solution {
    public:
        vector<vector<int>> pathSum(TreeNode* root, int sum) {
            vector<vector<int>>  result;
            vector<int> solution;
            help(root, sum, result, solution);
            return result;
        }
        
        void help(TreeNode* root, int sum, vector<vector<int>> &result, vector<int> solution){
            if(!root)   return;
            //leat node
            if(!root->left && !root->right && root->val==sum) {
                solution.push_back(root->val);
                result.push_back(solution);
                return;
            }
            //not leaf node
            solution.push_back(root->val);
            if(root->left)  {
                help(root->left, sum-root->val, result, solution);
            }
            if(root->right)  {
                help(root->right, sum-root->val, result, solution);
            }
        }
    };

  • 0
    Z

    Just want to point out, your program's space cost is too high as you need to maintain a vector<int> for each function call. I believe you can improve that by using a reference.


  • 0
    W

    If you do not use pass by reference for "paths" ( i.e., "vector<vector<int> >& paths" to "vector<vector<int> > paths" ), You don't need "path.pop_back();" anymore.


  • 0

    I love this passing by reference and pop_back idea


  • 0
    L

    My code is almost the same as yours but costs 24 ms... IDK why.

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        vector<vector<int>> pathSum(TreeNode* root, int sum) {
            vector<vector<int>> res;
            vector<int> currVct;
            helper(root, sum, res, currVct);
            return res;
        }
        
        void helper(TreeNode* root, int sum, vector<vector<int>>& res, vector<int> currVct) {
            if (!root) {
                return ;
            }
            sum -= root -> val;
            currVct.push_back(root -> val);
            if (!root -> left && !root -> right) {
                if (sum == 0) {
                    res.push_back(currVct);
                }
                return ;
            }
            helper(root -> left, sum, res, currVct);
            helper(root -> right, sum, res, currVct);
        }
    };

  • 0
    J

    @lijunray
    By the end of each recursive search, you need to pop_back() (delete the number) if the search fails. If you don't have this step, the code will return a traversal of the whole branch (because you have tried all possible leaves in the tree).


  • 1
    L

    @justin40 Thank you!


  • 0
    V

    This works without the last line of pop_back(). I think its not required


  • 0
    J

    @vjadon
    I comment-out the line. The result includes all the fail paths as I expected. Can you post your accepted code? Maybe we are using different method.


  • 0
    V

    @justin40
    class Solution {
    public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
    vector<vector<int>> res;
    vector<int> temp;
    hasPathSum(root,sum,res,temp);
    return res;
    }
    void hasPathSum(TreeNode* root, int sum,vector<vector<int>> &res,vector<int> temp) {

        if(root==NULL)
            return;
        temp.push_back(root->val);
        if(root->val==sum && root->left==NULL && root->right==NULL)
        {
             res.push_back(temp);
        }
         hasPathSum(root->left,sum-root->val,res,temp);
         hasPathSum(root->right,sum-root->val,res,temp);
       
    }
    

    };


  • 0
    J

    @vjadon
    I see the difference. Instead of passing the temp vector by reference, you pass it by value. Every instance of hasPathSum() keeps its own copy of temp vector and can only make changes to this copy. So, that's why you don't need to pop back every time.


  • 0
    V

    @justin40 true. It works in this case, but is it the best practice?


  • 0
    J

    @vjadon
    I would suggest you to do it by passing the vector as a reference. By passing the value, the memory required grow exponentially with each tree level (1 vector->2 vectors->4 vectors->....) and they all stay alive until the end of the recursion.


Log in to reply
 

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