C++. Pretty simple.


  • 0
    H
    /**
     * 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>> paths;
            vector<int> path;
            
            __pathSum(root , sum , path , paths);
            return paths;
        }
        
        void __pathSum(TreeNode *root , int sum , vector<int> &path , vector<vector<int>> &paths){
            if(!root)
                return ;
            path.push_back(root->val);
            if(!root->left && !root->right){
                if(sum == root->val){
                 paths.push_back(path);   
                }
            }else{
             __pathSum(root->left , sum-root->val , path , paths);   
             __pathSum(root->right , sum-root->val,path , paths);
            }
            path.pop_back();
        }
        
    };
    

    To solve this problem , While traversing we are doing two main
    operations:
    1.Storing the current path in a new vector and keep pushing elements in that vector.

    1. Subtracting the current elements value from the sum. Calling this recursively , if we reach the last node , we will see if the current
      sum = root->val, then we got the path and push to the resulting
      vector.
    2. The tricky part is that we have to pop the elements after it has been processed.

Log in to reply
 

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