113. Path Sum II | leetcode solution

 113. Path Sum II

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.

A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.

 

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: []

Example 3:

Input: root = [1,2], targetSum = 0
Output: []

 

Constraints:

• The number of nodes in the tree is in the range [0, 5000].
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

solution:

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}

 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

 * };

 */

class Solution {

public:

    void find_path(TreeNode* root , int ts , vector<vector<int>>&result , vector<int> insert , int sum)

    {   

        insert.push_back(root->val);

         sum = sum + root->val;

        if(sum == ts && root->left == NULL && root->right == NULL)

        {

             result.push_back(insert);

             return;

        }

          

         

         

         

        if(root->left != NULL)

        {

           find_path(root->left , ts , result , insert, sum);

        

        }

        if(root->right != NULL)

        { 

            find_path(root->right , ts , result , insert, sum);

        }

        

    }

    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {

         

        vector<vector<int>>result;

        vector<int>insert;

        int sum = 0;

        if(root == NULL)

            return result;

        find_path( root , targetSum , result , insert , sum);

        return result;

    }

};