[回溯法][树]leetcode113：路径总和 Ⅱ (medium)

总和 Ⅱ (medium)"/>

[回溯法][树]leetcode113：路径总和 Ⅱ (medium)

题目：

题解：

• 回溯法
• 对于树形结构采用dfs的策略寻找所有可行解，就是运用的回溯法。在到达叶子节点且节点值等于sum的剩余值表示找到一个可行解，若不等于表示没有找到可行解，则我们需要回溯到上一步。细节问题，可见代码。

代码如下：

class Solution {
public:vector<vector<int>> res;vector<int> path;vector<vector<int>> pathSum(TreeNode* root, int t) {dfs(root,t);return res;}void dfs(TreeNode* root,int t){if(!root)return;t-=root->val,path.push_back(root->val);if(!root->right and !root->left and !t)res.push_back(path);dfs(root->left,t),dfs(root->right,t);// 等到回溯到分支时就删除之前添加的节点t+=root->val,path.pop_back();}
};