首页 > 其他 > 详细

LeetCode OJ:Path Sum II(路径和II)

时间:2015-10-26 21:59:28      阅读:144      评论:0      收藏:0      [点我收藏+]

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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!