AcWing offer 34. 【回溯】二叉树中值为某数的路径
原题链接
中等
作者:
大明湖的鱼
,
2021-01-30 00:50:08
,
所有人可见
,
阅读 316
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<int> tmp;
dfs(root,sum,tmp);
return res;
}
void dfs(TreeNode* node ,int target,vector<int>& tmp){
if(node == NULL) return ;
tmp.emplace_back(node->val);
target -= node->val;
if(target == 0 && node->left == NULL && node->right == NULL)
res.emplace_back(tmp);
else {
dfs(node->left,target,tmp);
dfs(node->right,target,tmp);
}
tmp.pop_back();
}
};