二叉树路径求和逻辑

Question

我试图理解代码中的逻辑来解决Path Sum。这是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的逻辑与问题的基本逻辑总和作为价值。

谁能简化和解释？

Answer 1

让我们在执行过程中的某个地方选择函数。跳过计数增加的第一部分。接下来的两条指令与记录有多少相同的runningSums有关：如果我们已经看到它，则递增;否则，为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的正确孩子的某个地方再次到达B。对于我们发现的两个新段总计为12，我们再次将计数增加2。在完成B的两个子树之后，我们减少了为runningSum 8存储的值，因为我们已经计算了可以从那里开始的所有有效段。

最后一条指令“map.remove（runningSum）;”对我来说似乎不对。它应该是“减量”，否则我们将无法正确计算从A开始的节点，这些节点在节点B之前转到右边的孩子。你可以在这里找到这个观察的确认：https://github.com/katlew/Cracking-Coding-Interview/blob/master/chapter_4/pathsWithSum.java

Answer 2

您必须找到所有可能的路径，因此需要所需总和的频率。如果你计算++，答案只计算一条路径而不是所有可能的路径。

请考虑以下示例：

                    2
             3             4
         1     4        3     1

现在考虑路径2-> 3-> 4和2-> 4-> 3它们总和为相同的值，但它们是2个不同的路径。如果仅将计数增加1，则会错过另一条路径，因此需要频率。