題目: LeetCode - 437. Path Sum III
題目說明
給一個 Tree、一個整數 sum
,求樹中有幾段子樹的路徑和為 sum
。
解題思路
遍歷整棵樹,currSum
紀錄從 root
到當前節點的路徑和,由於 currSum - (currSum - target) = target
,所以只要看前面有幾種路徑和的值為 currSum - target
就可以得到以當前節點為終點的子樹路徑和為 sum
的個數,將次數加上 count
即可。
參考解法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| static auto __ = []() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0; }(); class Solution { public: int pathSum(TreeNode* root, int sum) { int count = 0; ++_m[0]; traverse(root, 0, sum, count); return count; } private: unordered_map<int, int> _m; void traverse(TreeNode* root, int currSum, int target, int& count) { if(!root) return; currSum += root->val; count += _m[currSum - target]; ++_m[currSum]; traverse(root->left, currSum, target, count); traverse(root->right, currSum, target, count); --_m[currSum]; } };
|