二叉树路径和逻辑

Question

我在尝试理解代码中解决路径总和问题的逻辑。这是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存储为键的逻辑，以及如果某些连续节点加起来等于tgtSum，那么(runningSum - tgtSum)的值必须存在于地图中作为其中一个键的价值，因为该差异将是其他节点的runningSum。

我不明白的是，为什么我们不能用count++替换count += map.get(runningSum - tgtSum)？

我尝试进行调试，我可以看到，在某些情况下，如果同一分支具有多个连续节点加起来等于tgtSum，则使用count++仅计算一次，而使用地图中存储的频率上述方式给出了正确的输出。

尽管我在花时间调试后成功了，但我无法将更新变量count的这部分逻辑与使用runningSum作为键和该运行总和的频率作为值的地图的基本逻辑联系起来。

有人能简化并解释吗？

- rgamber

Answer 1

让我们从执行过程中间开始选择函数。跳过计数增加的第一部分。接下来的两个指令与记录已记录的相同runningSum的数量有关：如果我们已经看到它，则增加；否则，将一个计数分配给runningSum键。

现在让我们回到增加计数的指令。假设当tgtSum为12时，我们已经达到了runningSum 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。同样，对于我们发现的两个新线段之和为12，我们将计数增加2。在完成B的两个子树后，我们减少存储在runningSum 8中的值，因为我们已经计算了所有可能从那里开始的有效线段。

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

- גלעד ברקן

---

谢谢！还有，我已经更正了最后一条指令，你是对的，它是错误的。我没有注意到这个问题！ - rgamber

Answer 2

你需要找到所有可能的路径，因此需要计算所需总和的频率。如果你使用 count++，答案只会计算其中一条路径，而不是所有可能的路径。

考虑以下示例：

                    2
             3             4
         1     4        3     1

现在考虑路径2->3->4和2->4->3，它们都加起来等于相同的值，但它们是两条不同的路径。如果你只增加计数器1次，你会错过另一条路径，因此需要频率统计。

- uSeemSurprised

---

我在调试后得出了这个结论，正如我在问题中提到的那样。我的问题是我无法将这个逻辑与问题的基本逻辑连接起来，因此寻求的是更多“直觉”式的答案而不是技术性的答案。不过还是感谢您的帮助！ - rgamber