黑车公司

1. /**
   
2. * Definition for a binary tree node.
   
3. * struct TreeNode {
   
4. *     int val;
   
5. *     TreeNode *left;
   
6. *     TreeNode *right;
   
7. *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
   
8. * };
   
9. */
   
10. class Solution {
    
11. public:
    
12.     void helper(TreeNode* root, int sum, map<int, vector<vector<int>>> pathSum, int curr_sum, vector<int> curr_path, int& numOfPath, vector<vector<int>>& paths) {
    
13.         if (!root) {
    
14.             return;
    
15.         }
    
16.         curr_sum += root->val;
    
17.         if (pathSum.count(curr_sum - sum)) {
    
18.             numOfPath += pathSum[curr_sum - sum].size();
    
19.             for (auto i:pathSum[curr_sum - sum]) {
    
20.                 vector<int> temp;
    
21.                 for (int cnt = i.size(); cnt < curr_path.size(); cnt++) {
    
22.                     temp.push_back(curr_path[cnt]);
    
23.                 }
    
24.                 temp.push_back(root->val);
    
25.                 paths.push_back(temp);
    
26.             }
    
27.         }
    
28.         curr_path.push_back(root->val);
    
29.         pathSum[curr_sum].push_back(curr_path);
    
30.         
    
31.         helper(root->left, sum, pathSum, curr_sum, curr_path, numOfPath, paths);
    
32.         helper(root->right, sum, pathSum, curr_sum, curr_path, numOfPath, paths);
    
33.     }
    
34.     int pathSum(TreeNode* root, int sum) {
    
35.         int numOfPath = 0;
    
36.         map<int, vector<vector<int>>> pathSum;
    
37.         pathSum[0].push_back(vector<int>());
    
38.         vector<int> cur_path;
    
39.         vector<vector<int>> paths;
    
40.         helper(root, sum, pathSum, 0, cur_path, numOfPath, paths);
    
41.         for (auto i:paths) {
    
42.             for (auto j:i) cout << j << " -> ";
    
43.             cout << endl;
    
44.         }
    
45.         return numOfPath;
    
46.     }
    
47. };

复制代码

及其耗空间的解法  不过如果时间只有45min  我也只能想到这样了  用lc437测了下 应该是对的

anoyanoy 发表于 2018-7-14 19:54
[mw_shl_code=cpp,true]/**
* Definition for a binary tree node.
* struct TreeNode {

👍

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

多谢楼主分享！
是和蠡口斯伞其一样只能从某个节点往下加吗？还是说可以任意方向加？

cynthiacao 发表于 2018-8-20 08:09
多谢楼主分享！
是和蠡口斯伞其一样只能从某个节点往下加吗？还是说可以任意方向加？

任意方向

楼主可以分享一下你的面试官名字吗

love_ballon 发表于 2018-7-12 08:41
烙印也不全不好了。我刚过的一个面试就是印度人。挺好的。我fail的都不是烙印，当然从来没遇到过国人。。。 ...

+1, 从来没有被烙印黑过, 遇到了很多烙印, 感觉都挺实诚的

原题啊亲。。