PathSumIIIOPT2 [source code]


public class PathSumIIIOPT2 {
static

public class Solution {
    public int pathSum(TreeNode root, int sum) {
        HashMap<Integer, Integer> preSum = new HashMap();
        preSum.put(0,1);
        return helper(root, 0, sum, preSum);
    }

    public int helper(TreeNode root, int currSum, int target, HashMap<Integer, Integer> preSum) {
        if (root == null) return 0;

        currSum += root.val;
        int res = preSum.getOrDefault(currSum - target, 0);
        preSum.put(currSum, preSum.getOrDefault(currSum, 0) + 1);

        res += helper(root.left, currSum, target, preSum) + helper(root.right, currSum, target, preSum);
        preSum.put(currSum, preSum.get(currSum) - 1);
        return res;
    }
}

    public static void main(String[] args) {
        PathSumIIIOPT2.Solution tester = new PathSumIIIOPT2.Solution();
    }
}

这个是 submission 最优解: 19(87);

好像跟前面的作者是同一个人?
应该是, 另外这个版本是 discussion 最优解, 是他公开的版本;
这个算法确实属于一个超级巧妙和难以理解的算法, 建议看下面的内容. 这里还是专门讲我对这个算法的一些理解;
看完下面的解释, 整体算法的思路应该是有了, 这里他细节处理上有两个地方可能不是特别好理解: 

res += helper(root.left, currSum, target, preSum) + helper(root.right, currSum, target, preSum);  
preSum.put(currSum, preSum.get(currSum) - 1);

首先, 我们要看到这里是一个Post Order 的过程, 当前这个 root 给 currSum 的 frequency 贡献了+1, 然后这个值要被向下的两个 child 使用, 因为向下的两个 child 是在同样的 path 上更深的地方, 也就是从最开始的大 root 到他们的path, 是包含当前这个node 的. 然后等到这两个 child 都处理完了(Post Order), 我们就开始网上回头, 上行, 这个是 DFS 的顺序, 脑子里要有概念, 这个时候我们将离开the subtree rooted at this node, 那么我们对于 map 的改动也必须在离开的时候撤销;

更宏观的角度来说, 这个撤销的操作, 就是体现了这个问题 DFS 的方面. 前面的算法看起来就是在一个单个的path 上操作的话, 不难理解, 但是你怎么能够推断他这个代码在一个 tree 上面也能够成立? 就是因为这里的这个 DFS 撤销操作. 当你站在某一个 node, 你确保你这个 node 向下(也就是这个 node 自己的 subtree), 跟向上(这个subtree 以外的地方)有完整的分割(区别);

总体来说这个算法真的是非常聪明;

另外如果看下面, 可以看到, 作者将这个算法跟2sum 进行了类比, 那么这两个算法究竟有什么类似的地方呢?
仔细想想2sum: 比如我们要找 sum 等于10, 那么我们碰到2的时候, 我们存<8=indexof(2)>; 后面我们碰到8的时候, 直接就可以查询到; 这个算法可以换一个角度理解: 我们碰到2, 存<2=indexof(2)>, 然后碰到8的时候, 我们查询key = target - 8 = 2;
这里: 我们要找长度为10的一个 path, 我们碰到一个 currSum 是2的 node, 我们存下来<2=freqof(2)>; 后面我们碰到一个 currSum 是12的 node, 我们直接查询的key 就是2, 然后我们找到了2; 我们查询的 key 是 key = currSum - target;
看到没有, 这两个问题确实是有共性的. 只能说这个作者的悟性真的是点满了;

虽然我们前面解释过 HashTable historical stream 类问题的一般思路了, 但是这里这个问题对于HashTable 的理解显然要求的更加深刻. HashTable 里面的key, 一般来说更多的应该是与每一个 element 紧密联系的一个值, 比如2sum 里面的, 存的其实就是自己的 value; 而在这个 PathSum 里面, 存的其实就是自己的 currSum, 或者叫 preSum.
这个作为 HashTable 的 key 的 value 有两个共同特点:

  1. specifically associated with each element. 在2sum 里面每个element 就是一个entry, 在这里, 是一个 node;
  2. can be used to calculate the target directly. 这个还是很好理解的;

这两个问题合并理解, 对于加深理解怎么解决 HashTable 历史信息类问题, 尤其是 HashTable 的 key 怎么选择, 有重要的学习意义;

另外你换一个角度来看: preSum1 - preSum2 = target, 这个式子是这个算法的核心. 这个式子本身也是符合我们之前include root in recursive return value to enable DP property的一个经验: 每一个 preSum 都是跟 root 直接挂钩的, 而且勉强可以说是拥有 DP Property.

这个是作者自己的解释:
So the idea is similar as Two sum, using HashMap to store ( key : the prefix sum, value : how many ways get to this prefix sum) , and whenever reach a node, we check if prefix sum - target exists in hashmap or not, if it does, we added up the ways of prefix sum - target into res.
For instance : 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 is 2, then we will have{2}, {1,2,-1}, {2,-1,-1,2} and {2}ways.

I used global variable count, but obviously we can avoid global variable by passing the count from bottom up. The time complexity is O(n).

The idea behind the code is: When I come to one node, I want to find all paths ended with current node, whose sum equal to target.

这个算法确实不好理解, 刚开始如果很难看得懂, 可以考虑从全是正数的一个tree/path 来思考; 简单升级;
以下是另外一些有用的 comment:

1

This solution makes me confused at first and seems others are having the same problem.

The idea is based on path.
Suppose now the hash table preSum stores the prefix sum of the whole path. Then after adding current node's val to the pathsum, if (pathsum-target) is in the preSum, then we know that at some node of path we have a (pathsum-target) preSum, hence we have a path of target. Actually, it is the path starting from that node.

Now the problem is how to maintain this preSum table? Since one path's preSum is different from others, we have to change it. However, we should notice that we can reuse the most part of the preSum table. If we are done with current node, we just need to delete the current pathsum in the preSum, and leave all other prefix sum in it. Then, in higher layers, we can forget everything about this node (and its descendants).
That's why we have

preSum.put(sum, preSum.get(sum) - 1);
// this deletes current pathsum and leave all previous sums
After running the algorithm, the preSum table should contain keys of all possible path sum starting from root, but all values of them are 0, except key 0. For instance in the example we should have:

{0: 1, 7: 0, 10: 0, 15: 0, 16: 0, 17: 0, 18: 0, 21: 0}
Hope it helps.

2

这一个特别详细;
This is an excellent idea and really took me some time to figure out the logic behind.
Hope my comment here could help others in understanding this solution.

  1. The prefix stores the sum from the root to the current node in the recursion
  2. The map stores 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:
  9. the total number of valid paths in the subtree rooted at the current node's left child
  10. the total number of valid paths in the subtree rooted at the current node's right child
  11. 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. 现在是18ms 了; 

public int pathSum(TreeNode root, int sum) {  
    if (root == null) {  
        return 0;  
    }  
    Map<Integer, Integer> map = new HashMap<>();  
    map.put(0, 1);  
    return findPathSum(root, 0, sum, map);    
}  
private int findPathSum(TreeNode curr, int sum, int target, Map<Integer, Integer> map) {  
    if (curr == null) {  
        return 0;  
    }  
    // update the prefix sum by adding the current val  
    sum += curr.val;  
    // get the number of valid path, ended by the current node  
    int numPathToCurr = map.getOrDefault(sum-target, 0);   
    // update the map with the current sum, so the map is good to be passed to the next recursion  
    map.put(sum, map.getOrDefault(sum, 0) + 1);  
    // add the 3 parts discussed in 8. together  
    int res = numPathToCurr + findPathSum(curr.left, sum, target, map)  
                                           + findPathSum(curr.right, sum, target, map);  
   // restore the map, as the recursion goes from the bottom to the top  
    map.put(sum, map.get(sum) - 1);  
    return res;  
}

3

I see a lot of comments couldn't understand the logic behind it:
Here is my way to understand it

  1. each time it looks for (x=curr_sum - target) from HashMap, you can translate it as target = curr_sum-x(x is what we are looking for in HashMap)
  2. if x exists in Hash, that is to say we can find a point that sum(from root to this point) == x, if we start from this point+1， we do a minus operation (curr_sum-x) from curr_sum thus get the target.

4

@kekezi

Very understandable explanation!

I got stuck with the solution for almost 4 hrs and it comes that the whole strategy is different from mine:

My Solution is like a top down approach:

of path = pathSum(root.left, sum) + pathSum(root.right, sum) + findPathStartingFrom(root).

and findPathStartingFrom(root) = FindPathStartingFrom(root.left, sum - root.val) + FindPathStartingFrom(root.right, sum - root.val).

But for the hashmap presum approach, the recursive solution is like:

the objective of the algorithm:
summation of all possible # of path ended at the each node in the tree.

This insight can lead to another recursive relation:

pathSum(root) = # of path ended at root + pathSum(root.left) + pathSum(root.right)

To calculate the # of path in the current subtree except the current root: pathSum(curr.left, sum, currSum, map) + pathSum(curr.right, sum, currSum, map)

To calculate the # of path ended at the current root: it is map.getOrDefault(currSum - target, 0).

Thus the final result is the sum of the above 2 statements.

Problem 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
    Difficulty:Easy
    Category:Algorithms
    Acceptance:39.49%
    Contributor: Stomach_ache
    Related Topics
    tree
    Similar Questions
    Path Sum Path Sum II

results matching ""

    No results matching ""