首页 > 代码库 > Path Sum II
Path Sum II
Given a binary tree and a sum, find all root-to-leaf paths where each path‘s sum equals the given sum.
For example:
Given the below binary tree and sum = 22
,
5 / 4 8 / / 11 13 4 / \ / 7 2 5 1
return
[ [5,4,11,2], [5,8,4,5]]
分析:此题可以用DFS解,当遍历到叶节点时,判断当前path的sum是否等于target sum,如果相等便将当前path加入到result中。
代码如下:
1 class Solution { 2 public: 3 vector<vector<int> > pathSum(TreeNode *root, int sum) { 4 vector<vector<int>> res; 5 if(!root) return res; 6 vector<int> path; 7 dfs(res,path,root,0,sum); 8 return res; 9 }10 void dfs(vector<vector<int>> & res, vector<int> & path,TreeNode * root, int pre_sum, int sum){11 if(!root) return;12 path.push_back(root->val);13 int cur_sum = pre_sum + root->val;14 dfs(res,path,root->left,cur_sum,sum);15 dfs(res,path,root->right,cur_sum,sum);16 if(cur_sum == sum && !root->left && !root->right) res.push_back(path);17 path.pop_back();18 }19 };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。