首页 > 代码库 > Path Sum II

Path Sum II

2024-07-17 08:37:41   219人阅读

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 };

 


联系
我们