113. Path Sum II

https://leetcode.com/problems/path-sum-ii/

本题大意：给定一个二叉树和一个值sum，求出所有从根节点到叶子节点的路径，使得路径所通过的节点值之和为sum。

例如：给定二叉树：　　　　　　　　　　　　　　值为sum=22，所得结果应该为：

解题思路：路径要满足的条件为：1、相加之和等于sum 2、最终应该到叶子结点。这两个也就是递归成功的返回条件。递归不成功的返回条件为：1、到达了叶子结点 2、但是相加之和不为sum。

本题是先序遍历的递归：肯定是先考察当前结点，然后递归左子树，再递归右子树。

注意：回溯问题。如果当前这颗子树的左右子树都遍历完了，那么应该回到它的父节点。

代码如下：

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     vector<vector<int>> pathSum(TreeNode* root, long long sum) {
13         vector<int> v;
14         vector<vector<int> > path;
15         pathSumHelper(v, path, root, sum);
16         
17         return path;
18     }
19     
20     void pathSumHelper(vector<int> & v, vector<vector<int> > & path, TreeNode* root, long long sum)
21     {
22         if(!root) return;
23 
24         v.push_back(root->val);
25         int cur = sum - root->val;
26         if(!root->left && !root->right)
27         {
28             if(cur == 0)
29             {
30                 path.push_back(v);
31                 v.pop_back();
32                 return;
33             }
34             else
35             {
36                 v.pop_back();
37                 return;
38             }
39         }
40         pathSumHelper(v, path, root->left, cur);
41         pathSumHelper(v, path, root->right, cur);
42         v.pop_back();
43         return;
44     }
45 };