P143. 二叉树中和为给定值的路径数量

https://algocasts.io/episodes/Yopkb0G3

 private int dfs(TreeNode root, int cur, int sum, Map<Integer, Integer> prefixSum) {
    if (root == null) return 0;
    cur += root.val;
    // 想问下这里,视频讲解的时候使用的是sum-cur,
    // 为什么这里是cur - sum,另外如果调换顺序的话,
    // 程序的运行结果是不一致的,?没想明白哪里出的问题
    int cnt = prefixSum.getOrDefault(cur - sum, 0); 
    prefixSum.put(cur, prefixSum.getOrDefault(cur, 0) + 1);
    cnt += dfs(root.left, cur, sum, prefixSum);
    cnt += dfs(root.right, cur, sum, prefixSum);
    prefixSum.put(cur, prefixSum.get(cur) - 1);
    return cnt;
  }

@ShaunMurphy

帮你重新排版了一下,好看一些。论坛是支持 markdown 的,可以用 markdown 语法来写帖子。

回答

视频里说的也是 cur - sum,这里的 dfs 是视频里讲的第二种方法。cur 表示前缀和,是用前缀和减去 sum,来看差值是否为另一个前缀和。所以肯定是不能换过来用 sum - cur 的。

你说的 sum - cur,是第一种方法,用的是 sum 减去当前节点值。

1赞

好的,感谢!一连看了好几个视频,看混了。。。LOL;
多谢帮忙排版,共同维护更好的社区提问环境~加油!