首页 > 代码库 > 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"