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.

  1.               5
  2.              / \
  3.             4   8
  4.            /   / \
  5.           11  13  4
  6.          /  \      \
  7.         7    2      1

return

  1. [
  2.    [5,4,11,2],
  3.    [5,8,4,5]
  4. ]

题目翻译：
给定一个二叉树，并且给定一个值，找出所有从根节点到叶子节点和等于这个给定值的路径.上面的例子可以很好地让读者理解这个题目的目的.

解题思路:
这个题目和Path Sum的解法几乎是一模一样，都是用dfs来进行求解，不过就是在传参数的时候有些不同了，因为题目的要求也不同.

时间复杂度:
O(n)

代码如下:

  2. /**
  3.  * Definition for binary tree
  4.  * struct TreeNode {
  5.  *     int val;
  6.  *     TreeNode *left;
  7.  *     TreeNode *right;
  8.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  9.  * };
  10.  */
  11. class Solution {
  12. public:
  13.     vector<vector<int> > pathSum(TreeNode *root, int sum) {
  14.         vector<vector<int>> ret;
  15.         if(root == NULL)
  16.             return ret;
  17.         vector<int> curr;
  18.         DFS(ret,curr,sum,0,root);
  19.         return ret;
  20.     }
  22.     void DFS(vector<vector<int>>& ret, vector<int> curr, int sum, int tmpsum, TreeNode* root)
  23.     {
  24.         if(root == NULL)
  25.             return;
  26.         tmpsum+=root->val;
  27.         curr.push_back(root->val);
  28.         if(tmpsum == sum)
  29.         {
  30.             if(root->left == NULL&&root->right == NULL)
  31.             {
  32.                 ret.push_back(curr);
  33.                 return;
  34.             }
  35.         }
  36.         DFS(ret,curr,sum,tmpsum,root->left);
  37.         DFS(ret,curr,sum,tmpsum,root->right);
  38.     }
  39. };