Problem
题目大意：给你一棵二叉树，返回单向的路径和等于sum的路径数量。
https://leetcode.com/problems/path-sum-iii/description/
You are given a binary tree in which each node contains an integer value.
Find the number of paths that sum to a given value.
The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.
Example:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
Return 3. The paths that sum to 8 are:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
Solution 1: Recursion
Time complexity: O(n^2)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua // Running time: 21 ms class Solution { public: int pathSum(TreeNode* root, int sum) { if (!root) return 0; return numberOfPaths(root, sum) + pathSum(root->left, sum) + pathSum(root->right, sum); } private: int numberOfPaths(TreeNode* root, int left) { if (!root) return 0; left -= root->val; return (left == 0 ? 1 : 0) + numberOfPaths(root->left, left) + numberOfPaths(root->right, left); } }; |
Solution 2: Running Prefix Sum
Same idea to 花花酱 LeetCode 560. Subarray Sum Equals K
Time complexity: O(n)
Space complexity: O(h)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua // Running time: 13 ms (beats 97.74%) public: int pathSum(TreeNode* root, int sum) { ans_ = 0; sums_ = {{0, 1}}; pathSum(root, 0, sum); return ans_; } private: int ans_; unordered_map<int, int> sums_; void pathSum(TreeNode* root, int cur, int sum) { if (!root) return; cur += root->val; ans_ += sums_[cur - sum]; ++sums_[cur]; pathSum(root->left, cur, sum); pathSum(root->right, cur, sum); --sums_[cur]; } }; |
Related Problem
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment