总和 Ⅱ (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();}
};
更多推荐
[回溯法][树]leetcode113:路径总和 Ⅱ (medium)
发布评论