437. Path Sum III
1. 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.
2. Example
Example 1:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
Return 3. The paths that sum to 8 are:
- 5 -> 3
- 5 -> 2 -> 1
- -3 -> 11
3. Solutions
My Accepted Solution
n is the number of nodes in i_root
Time complexity: O($n^2$)
Space complexity: O(n)
class Solution
{
private:
int result = 0;
vector<int> pathValues; // use global variable or reference is faster than passing value
void preorderTraverse(TreeNode *i_root, int sum)
{
pathValues.push_back(i_root->val);
for(int i = pathValues.size() - 1, pathSum = 0; i >= 0; i--)
{
pathSum += pathValues[i];
if(pathSum == sum) result++;
}
if(i_root->left) preorderTraverse(i_root->left, sum);
if(i_root->right) preorderTraverse(i_root->right, sum);
pathValues.pop_back(); // pathValues is a global variable, we must delete the current node for others' use
}
public:
// int pathSum(TreeNode* root, int sum)
int pathSum(TreeNode *i_root, int sum)
{
if(!i_root) return 0;
preorderTraverse(i_root, sum);
return result;
}
};
3.1 PreSum Map
n is the number of nodes in i_root
Time complexity: O(n)
Space complexity: O(n)
// at my own solution, for every node, I calculate all possible sum
// but this process will be duplicate, since the previous sum has been calculated
// for example, 1 -> 2 -> 3 -> 4, when we process 4, we calculate 1+2+3+4, but 1+2+3 has been calculated when we dealing with 3
// so we could use a presum map to store them and don't need to calculate them again and again, like DP thinking
class Solution
{
private:
int result = 0;
map<int, int> numberOfSum;
void preorderTraverse(TreeNode *i_root, int sum, int currentPathSum)
{
currentPathSum += i_root->val;
result += numberOfSum[currentPathSum - sum];
numberOfSum[currentPathSum]++;
if(i_root->left) preorderTraverse(i_root->left, sum, currentPathSum);
if(i_root->right) preorderTraverse(i_root->right, sum, currentPathSum);
numberOfSum[currentPathSum]--;
}
public:
// int pathSum(TreeNode* root, int sum)
int pathSum(TreeNode *i_root, int sum)
{
if(!i_root) return 0;
numberOfSum[0] = 1; // empty
preorderTraverse(i_root, sum, 0);
return result;
}
};