9ms Simple C++


  • 0
    A

    First, it's a preorder traversal, because you are interested in a potential path from root to leaf.

    The potential vector is a potential path that you are trying as you traverse down the tree.
    The res vector is what you are going to return in the end.

    If you find potential path that has the given sum, you simply add it to the res vector.

    As you backtrack, you want to discard the current node you are returning from -- a.k.a potential.pop_back()
    This will allow for correct branching.

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

Log in to reply
 

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