/*
437. Path Sum III

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


Think:
There's a great explanation on the discussion by Kekezi
DP+Memorization <-- perfect

I only mention the 2nd step with a sample
"""
The sum from any node in the middle of the path to the current node = the difference between the sum from the root to the current node and the prefix sum of the node in the middle
"""

if there's a subtree [1,2,3] and target is 3, due to top-down method, you will store
1 first. (Memorization)
Then go left, and you will get 3( 1+ 2) in memorization. For sure, it is a valid path
Take the other side, and you will get 4(1+3) in memorization.
Meanwhile, If we could possibly get rid of this one node in the middle, and we will get valid path, which means 4 - 3.
We now check the memorization, there's 1 in the memorization, so 1->3 would be a valid answer w/o 1.

Take other example w/ negative one. [-2,1,-1] -1
[-2] at first
-2->1 would be an answer
-2->-1 w/o -2 would be answer (-3-(-1))

Detailed example for question




map[0:1] &{10 0xc42000a1a0 0xc42000a1c0}
-->10, 10, 2, 0
&map[0:1 10:1] &{5 0xc42000a200 0xc42000a220}
-->5, 15, 7, 0
&map[0:1 10:1 15:1] &{3 0xc42000a260 0xc42000a280}
-->3, 18, 10, 1
&map[18:1 0:1 10:1 15:1] &{3 <nil> <nil>}
-->3, 21, 13, 0
&map[21:1 0:1 10:1 15:1 18:1] <nil>
&map[10:1 15:1 18:1 21:1 0:1] <nil>
&map[0:1 10:1 15:1 18:1 21:0] &{-2 <nil> <nil>}
-->-2, 16, 8, 0
&map[21:0 16:1 0:1 10:1 15:1 18:1] <nil>
&map[0:1 10:1 15:1 18:1 21:0 16:1] <nil>
&map[16:0 0:1 10:1 15:1 18:0 21:0] &{2 <nil> 0xc42000a2a0}
-->2, 17, 9, 0
&map[15:1 18:0 21:0 16:0 17:1 0:1 10:1] <nil>
&map[16:0 17:1 0:1 10:1 15:1 18:0 21:0] &{1 <nil> <nil>}
-->1, 18, 10, 1
&map[0:1 10:1 15:1 18:1 21:0 16:0 17:1] <nil>
&map[10:1 15:1 18:1 21:0 16:0 17:1 0:1] <nil>
&map[0:1 10:1 15:0 18:0 21:0 16:0 17:0] &{-3 <nil> 0xc42000a240}
-->-3, 7, -1, 0
&map[10:1 15:0 18:0 21:0 16:0 17:0 7:1 0:1] <nil>
&map[18:0 21:0 16:0 17:0 7:1 0:1 10:1 15:0] &{11 <nil> <nil>}
-->11, 18, 10, 1
&map[17:0 7:1 0:1 10:1 15:0 18:1 21:0 16:0] <nil>
&map[15:0 18:1 21:0 16:0 17:0 7:1 0:1 10:1] <nil>

And the reference from Leetcode discussion.
-----------------------------------------------

This is an excellent idea and took me some time to figure out the logic behind.
Hope my comment here could help understanding this solution.


1. The prefix stores the sum from the root to the current node in the recursion
2. The map stores <prefix sum, frequency> pairs before getting to the current node. We can imagine a path from the root to the current node. The sum from any node in the middle of the path to the current node = the difference between the sum from the root to the current node and the prefix sum of the node in the middle.
3. We are looking for some consecutive nodes that sum up to the given target value, which means the difference discussed in 2. should equal to the target value. In addition, we need to know how many differences are equal to the target value.
4. Here comes the map. The map stores the frequency of all possible sum in the path to the current node. If the difference between the current sum and the target value exists in the map, 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.
5. Note that there might be multiple nodes in the middle that satisfy what is discussed in 4. The frequency in the map is used to help with this.
6. Therefore, in each recursion, the map stores all information we need to calculate the number of ranges that sum up to target. Note that each range starts from a middle node, ended by the current node.
7. To get the total number of path count, we add up the number of valid paths ended by EACH node in the tree.
8. 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 the top(root) to the bottom(leaves), and the result of total count is calculated from the bottom to the top :D

The code below takes 16 ms which is super fast.






*/

func pathSum(root *TreeNode, sum int) int {
    if root == nil {
        return 0
    }

    m := make(map[int]int) // bottom-up map and
    m[0]=1
    return backtrack(&m, root, 0, sum)
}

func backtrack(_m *map[int]int, root *TreeNode, sum, target int) int {
    fmt.Println(_m, root)
    if root == nil {
        return 0
    }
    sum += root.Val
    m := *_m
    numPathToCur := 0
    fmt.Printf("-->%d, %d, %d, %d\n",root.Val, sum, sum-target, m[sum-target])
    if _,ok := m[sum-target]; ok {
        numPathToCur = m[sum-target]
    }
    if _,ok := m[sum]; !ok {
        m[sum] = 1
    } else {
        m[sum] += 1
    }
    rst :=numPathToCur + backtrack(&m, root.Left, sum, target)+backtrack(&m, root.Right, sum, target)
    m[sum] -= 1
    return rst
}