开发者社区云计算文章正文

[LeetCode] Path Sum II

2015-07-11 890

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： Well, a typical backtracking problem. The code is as follows. You may walk through it using the example in the problem statement to see how it works.

Well, a typical backtracking problem. The code is as follows. You may walk through it using the example in the problem statement to see how it works.

 1 class Solution {
 2 public:
 3     vector<vector<int>> pathSum(TreeNode* root, int sum) {
 4         vector<vector<int> > paths;
 5         vector<int> path;
 6         findPaths(root, sum, path, paths);
 7         return paths;  
 8     }
 9 private:
10     void findPaths(TreeNode* node, int sum, vector<int>& path, vector<vector<int> >& paths) {
11         if (!node) return;
12         path.push_back(node -> val);
13         if (!(node -> left) && !(node -> right) && sum == node -> val)
14             paths.push_back(path);
15         findPaths(node -> left, sum - node -> val, path, paths);
16         findPaths(node -> right, sum - node -> val, path, paths);
17         path.pop_back();
18     }
19 };