首页 > 代码库 > 保存一棵树根到叶子之和为给定值的所有路径的DFS解法
保存一棵树根到叶子之和为给定值的所有路径的DFS解法
这道题目DFS用得非常不自信。
(1)递归的用得不够大胆,过分考虑细节了,应该站得高些。
(2)思路厘清之后,要注意状态值的修改,就是状态恢复。深度优先走到底之后,需要返回,此时对应的状态也应该返回。例如之前放到堆栈/vector里的状态数据要弹出来。
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: void dfs(vector<vector<int>> &res,vector<int> &path,TreeNode *root, int sum){ if(!root) return ; if(!root->left&&!root->right){ if(root->val==sum){ path.push_back(root->val); res.push_back(path); path.pop_back(); } else return; } sum=sum-root->val; path.push_back(root->val); dfs(res,path,root->left,sum); path.pop_back(); path.push_back(root->val); dfs(res,path,root->right,sum); path.pop_back(); } vector<vector<int> > pathSum(TreeNode *root, int sum) { vector<vector<int>> res; vector<int> path; dfs(res,path,root,sum); return res; } };
保存一棵树根到叶子之和为给定值的所有路径的DFS解法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。