LeetCode_Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.



For example:

Given the below binary tree and sum = 22,

              5

             / \

            4   8

           /   / \

          11  13  4

         /  \    / \

        7    2  5   1

return



[

   [5,4,11,2],

   [5,8,4,5]

]

/**

 * Definition for binary tree

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

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

 * };

 */

class Solution {

public:

   void DFS(TreeNode *root, vector<int> &temp, int tempSum)

    {

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

                result.push_back(temp);

                return;

        }

        

        if(root->left!= NULL ){

            temp.push_back(root->left->val);

            DFS(root->left, temp,root->left->val + tempSum );

            temp.pop_back();

        }

        

        if(root->right != NULL ){

            temp.push_back(root->right->val);

            DFS(root->right, temp, root->right->val + tempSum);

            temp.pop_back();

        }

    }

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

        // Start typing your C/C++ solution below

        // DO NOT write int main() function

        result.clear();

        if(!root) return result;

        this->sum = sum; 

        vector<int> temp;

        temp.push_back(root->val);

        DFS(root, temp, root->val);

        return result;

    }

private:

    int sum;

    vector<vector<int>> result;

};