二叉树中和为某一值的路径
题目链接:https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/
思路:递归,每次从target中减去当前节点的值,终止条件为判断到达叶子节点时target是否为0. 返回上层时把当前节点的值要pop出去。
参考代码:
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int target) {
vector<vector<int>> res;
if (!root) {
return res;
}
vector<int> path;
recursionSum(root, target, res, path);
return res;
}
void recursionSum(TreeNode* root, int target, vector<vector<int>>& res, vector<int>& path) {
if (!root) {
return;
}
path.push_back(root->val);
target -= root->val;
if (!root->left && !root->right) {
if (target == 0) {
res.push_back(path);
}
}
recursionSum(root->left, target, res, path);
recursionSum(root->right, target, res, path);
path.pop_back();
return;
}
};