思路
前序遍历谁都会,问题就是回溯的时候该在什么位置pop_back()。
前序遍历的特性是让根节点先入队,那么在回溯的时候当然也是在最后出队,所以就是d->l->r->d的顺序操作就可以了
/**
* 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:
vector<vector<int>> ans;
vector<int>temp;
void dfs(TreeNode* p,int cur,int target)
{
if(!p)return;
temp.push_back(p->val);//前序遍历,根左右,先进向量
if(!p->left&&!p->right&&cur+p->val==target)ans.push_back(temp);
dfs(p->left,cur+p->val,target);
dfs(p->right,cur+p->val,target);
temp.pop_back();//因为是前序遍历,所以回溯的时候是右左根,在最后出向量
}
vector<vector<int>> pathSum(TreeNode* root, int target) {
if(!root)return ans;
dfs(root,0,target);
return ans;
}
};