- /**
- * Definition for a binary tree node.
- * struct TreeNode {
- * int val;
- * TreeNode *left;
- * TreeNode *right;
- * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
- * };
- */
- class Solution {
- int ret;
- voidgo(TreeNode *p,intsofar,inttgt, unordered_map<int, unsigned> rec)
- {
- if(!p)return;
- sofar += p->val;
- if(sofar == tgt)
- {
- ret ++;// case 1 : from root
- }
- intt = sofar - tgt;
- if(rec.find(t) != rec.end())
- {
- ret += rec[t];
- }
- rec[sofar] ++;
- go(p->left, sofar, tgt, rec);
- go(p->right,sofar, tgt, rec);
- }
- public:
- intpathSum(TreeNode* root,int sum)
- {
- ret =0;
- if(!root)return 0;
- go(root, 0, sum, unordered_map<int, unsigned>());
- return ret;
- }
- };
来源: