Leetcode113
链接：力扣?。
题目：
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]
解释：
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22
思路：
与Leetcode112十分相似，但是本题需要找出所有路径。在112题中，其实暗含剪枝的思想。我们遍历的目的是为了到达叶结点并找到一条所需的路径。对于当前子树，只要左右孩子中发现了一条所需的路径，当前层就可以直接返回true，并如此反复将true传给最顶层。只要找到一条所需路径，后续所有到其他叶结点的遍历就可以中止直接向上层返回了，这样就减少了很多不需要的遍历。
而本题则需要老老实实将二叉树遍历完，找到所有所需路径。实际上，本题与257题基本相同，只需稍作修改即可。
依然使用递归的前序遍历思路。
用一个vector<vector<int> >数组result来记录最终答案，并用一个path数组记录当前已经走过的路径。
用前序遍历的方法。对于当前结点root，如果为空则return，若不为空，判断其是否为叶结点，如果非叶结点则将其加入path，并令sum与当前结点的val相加，依次递归进入其左子树和右子树，左右子树都递归完后还要从path里面删除该结点。
那么递归的边界在哪里呢？其实存在两个递归边界。
第一个边界就是当前结点为空时，直接return。
第二个边界就是当前访问结点为叶结点时，表示已经走完了一条路径，令sum与当前结点的val相加，判断其sum是否等于targetSum，如果相等将该叶结点加入path，然后将path全体加入加入result来记录一条结果。然后该叶结点从path里面删除。
参考代码：
/**
* 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 traversal (TreeNode *root, vector<int> &path, int targetSum) {
if (root == nullptr) {
return;
}
path.push_back(root->val);
if (root->left == nullptr && root->right == nullptr) {
int sum = 0;
for (int i = 0; i < path.size(); i++) {
sum += path[i];
}
if (sum == targetSum) {
result.push_back(path);
}
}
else {
traversal(root->left, path, targetSum);
traversal(root->right, path, targetSum);
}
path.pop_back();
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<int> path;
traversal(root, path, targetSum);
return result;
}
private:
vector<vector<int> > result;
};