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，代码如下：
1 class Solution { 2 public: 3 vector<vector<int>> pathSum(TreeNode* root, int sum) { 4 vector<int> res; 5 dfs(root, res, sum); 6 return ret; 7 } 8 9 void dfs(TreeNode * root, vector<int> res, int left) 10 { 11 if(!root) return; 12 if(!root->left && !root->right && left == root->val){ 13 res.push_back(root->val); 14 ret.push_back(res); 15 } 16 if(left <= root->val) 17 return; 18 else{ 19 res.push_back(root->val); 20 if(root->left) 21 dfs(root->left, res, left -= root->val); 22 if(root->right) 23 dfs(root->right, res, left -= root->val); 24 } 25 } 26 private: 27 vector<vector<int>> ret; 28 };
LeetCode OJ：Path Sum II（路径和II）
原文：http://www.cnblogs.com/-wang-cheng/p/4912308.html