# 437. Path Sum III

Reference: LeetCode

Difficulty: Easy

## Problem

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:**

1 | root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8 |

**Follow up:**

- Reduce the time complexity.

## Analysis

By fudonglai:

写递归的技巧是：明白一个函数的作用并相信它能完成这个任务，千万不要跳进这个函数里面企图探究更多细节，否则就会陷入无穷的细节无法自拔。你就算浑身是铁，能压几个栈？more按照前面说的技巧，先来定义清楚每个递归函数应该做的事：

pathSum 函数：给他一个节点和一个目标值，他返回以这个节点为根的树中，和为目标值的路径总数。

count 函数：给他一个节点和一个目标值，他返回以这个节点为根的树中，能凑出几个以该节点为路径开头，和为目标值的路径总数。

**Methods:**

- Typical Recursion
- First, we should define each recursive function’s job.
`pathSum(x, target)`

: Return the number of paths that satisfy`target`

requirement in a tree whose root is`x`

.`count(x, target)`

: Return the number of paths that satisfy`target`

requirement in a tree whose root**must be**`x`

, the head of those paths.**Time:**`11 ms`

- In each level in tree, as you go down, $N$ is halved, and finally you call
`count(x, target)`

for the leaves whose cost is $T(1)$ (not all the same $N$). Each layer does $O(N)$, and in the best case there are $\log{N}$ layers. - According to the master theorem,
`pathSum()`

: $T(N) = 2T(N/2) + O(N) = O(N\log{N})$`count()`

: $T(N) = 2T(N/2) + O(1)$

- Best: $O(N\log{N})$
- Worst: $O(N^2)$

- In each level in tree, as you go down, $N$ is halved, and finally you call
**Space:**$O(h)$

- HashMap + Prefix Sum (tankztc & kekezi)
**Time:**$O(N)$`4 ms`

**Space:**$O(N)$- The idea is similar as Two Sum, using
`HashMap`

to store keys (the prefix sum) and values (how many ways to get to this prefix sum). - The
`prefix sum`

stores the sum from the root to the current node in the recursion. - Whenever we reach a node, we check if
`prefix sum - target`

exists in the HashMap.- If it does, we added up the ways of
`prefix sum - target`

into result. - For example:
- In one path we have:
`[1, 2, -1, -1, 2]`

, - then the prefix sum will be:
`[1, 3, 2, 1, 3]`

. - Let’s say we want to find target sum $2$, then we have $4$ paths which are
`2`

,`1,2,-1`

,`2,-1,-1,2`

, and`2`

.

- In one path we have:

- If it does, we added up the ways of

- The sum from any node in the middle of the path to the current node
- $=$ (the sum from the root to the current node) $-$ (the prefix sum of the node in the middle)

- We want the difference above equal to the target value. In addition, we need to know how many differences are equal to the target value.
- Use
`HashMap`

. The`value`

of map stores the frequency of all possible sum in the path to the current node. If the difference we want exists, there must exist a node in the middle of the path, such that from this node to the current node, the sum is equal to the target value. - There might be multiple nodes in the middle that satisfy the requirement. In each recursion, the map stores all information we need to calculate the number of ranges that sum up to target (start from a middle node and end by the current node).
- To get the total number of a path count, we add up the number of valid paths ended by
`each`

node in the tree. - Each recursion returns the total count of valid paths in the subtree rooted at the current node. And this sum can be divided into three parts:
- The total number of valid paths in the subtree rooted at the current node’s left child.
- The total number of valid paths in the subtree rooted at the current node’s right child.
- The number of valid paths ended by the current node.

- The interesting part of this solution is that the prefix is counted from root to leaves, and the result of total count is calculated from the bottom to the top.

## Code

### Typical Recursion

#### Incorrect Version

First, let’s examine **an incorrect version**:

1 | public int pathSum(TreeNode root, int sum) { |

Example:

1 | Input = [1,null,2,null,3] |

Call Stack:

1 | p(1, 3, 3) |

We can see that there are repeated calculations.

`p(3, 3, 3)`

called by`p(2, 2, 3)`

called by`p(1, 3, 3)`

.`p(3, 3, 3)`

called by`p(2, 3, 3)`

called by`p(1, 3, 3)`

.

#### Correct Version

1 | // pathSum(): How many paths in a tree whose head is root satisfy? |

### HashMap + Prefix Sum

**Note:**

- I am dead.

1 | public int pathSum(TreeNode root, int sum) { |