java - 二叉树路径总和逻辑

我试图理解代码中解决路径求和的逻辑。 Gayle Laakmann McDowell的书中这是一个已解决的问题，尽管我的代码看起来有些不同。

问题:给定一个二叉树，每个节点包含一个整数值，计算所有(向下)总和为目标值的路径。

代码:

private Map<Integer, Integer> map = new HashMap<>();
private int count = 0;

private int pathSum(BinaryTreeNode root, int tgtSum)
{
    map.put(0, 1);
    pathSum(root, 0, tgtSum);
    return count;
}

private void pathSum(BinaryTreeNode root, int runningSum, int tgtSum)
{
    if (root == null) return;

    runningSum += root.data;

    if (map.containsKey(runningSum - tgtSum))
    {
        count += map.get(runningSum - tgtSum);
    }

    if (map.containsKey(runningSum))
    {
        map.put(runningSum, map.get(runningSum) + 1);
    }
    else
    {
        map.put(runningSum, 1);
    }

    pathSum(root.left, runningSum, tgtSum);
    pathSum(root.right, runningSum, tgtSum);

    map.put(runningSum, map.get(runningSum) - 1);
}

我的问题:

我(有点)理解将runningSum作为键存储在映射中的逻辑，如果某些连续节点加到(runningSum - tgtSum)上，则tgtSum的值必须作为映射中的键之一存在，因为这种差异将是其他某个节点的runningSum。

我无法理解的是，为什么我们不能取代
带count += map.get(runningSum - tgtSum)的count++吗？

我尝试对其进行调试，在某些情况下，如果同一分支有多个连续的节点加到tgtSum，我可以看到，使用count++仅计数一次，而使用存储在映射中的频率，上述方法给出了正确的输出。

尽管花了一些时间调试后我就能够正确解决问题，但我无法通过使用以count为键的映射和运行频率将更新runningSum变量的逻辑这一部分与问题的基本逻辑联系起来总和作为值。

谁能简化和解释？

最佳答案

让我们在执行过程中的某个地方选择函数。跳过递增计数的第一部分。接下来的两条指令与记录多少相同的runningSum记录有关:如果已经看到，则递增；否则，为runningSum键分配一个计数。

现在让我们回到指令递增计数。想象一下，当runningSum为12时我们已经达到tgtSum 20，并且地图中已经记录了一个20 - 12 = 8密钥。这意味着在到达当前位置的某个较早节点上，runningSum为8。

                           ...
                           ...
         A  (runningSum 8) •
                          /
          (runningSum 7) • (-1)
                        /
     B  (runningSum 8) • 1
                      / \
     (runningSum 11) • 3 ...
                    /    ...
C  (runningSum 20) • 9
                   ...
                   ...

我们需要计算从A到C的路径以及从B到C的路径，因此我们将到目前为止的runningSum 8总数(存储为地图中键8的值)相加，代表了所有从一个节点，其runningSum为8，结束于我们当前所在的位置(本例中为2个分段)。

现在假设我们再次到达runningSum 20，在B的右子元素下方。再次，我们将两个新段的计数加2，总计为12。在完成B的两个子树之后，我们减少了为runningSum 8存储的值，因为我们已经计算了所有可能从此处开始的有效段。

最后一条指令“map.remove(runningSum);”对我来说似乎是错误的。应该是“减量”，因为否则我们将无法正确计算从A开始的，在节点B之前到达正确子节点的段。您可以在此处找到对此观察的确认:https://github.com/katlew/Cracking-Coding-Interview/blob/master/chapter_4/pathsWithSum.java