给定一个二叉树，找出所有路径中各节点相加总和等于给定 目标值 的路径。
一个有效的路径，指的是从根节点到叶节点的路径。
样例
样例1:
输入:
{1,2,4,2,3}
5
输出: [[1, 2, 2],[1, 4]]
说明:
这棵树如下图所示：
1
/
2 4
/
2 3
对于目标总和为5，很显然1 + 2 + 2 = 1 + 4 = 5
样例2:
输入:
{1,2,4,2,3}
3
输出: []
说明:
这棵树如下图所示：
1
/
2 4
/
2 3
注意到题目要求我们寻找从根节点到叶子节点的路径。
1 + 2 + 2 = 5, 1 + 2 + 3 = 6, 1 + 4 = 5
这里没有合法的路径满足和等于3.
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/*
* @param root: the root of binary tree
* @param target: An integer
* @return: all valid paths
*/
vector<vector<int>> binaryTreePathSum(TreeNode * root, int target) {
// write your code here
if (root == NULL) return {};
vector<vector<int>> res;
vector<int> path;
findPath(res, path, root, target);
return res;
}
static void findPath(vector<vector<int>>& res, vector<int>& path, TreeNode * root, int target) {
path.push_back(root->val); // pair-op <1>
target -= root->val;
if (root->left == NULL && root->right == NULL) {
if (target == 0) {
res.push_back(path); // update result
}
path.pop_back(); // pair-op <1>
return;
} // end condition, leaf node
if (root->left) findPath(res, path, root->left, target);
if (root->right) findPath(res, path, root->right, target);
path.pop_back(); // pair-op <1>
return;
}
};