首页 > 代码库 > LeetCode "437. Path Sum III"
LeetCode "437. Path Sum III"
The punch line of this one: sum of leaves: pi..pj = root..pj - root..pi.
/** * 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; void go(TreeNode *p, int sofar, int tgt, unordered_map<int, unsigned> rec) { if(!p) return; sofar += p->val; if(sofar == tgt) { ret ++; // case 1 : from root } int t = 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: int pathSum(TreeNode* root, int sum) { ret = 0; if(!root) return 0; go(root, 0, sum, unordered_map<int, unsigned>()); return ret; }};
LeetCode "437. Path Sum III"
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。