algorithm - 如果每个节点是其下所有节点的权重之和，则在树中找到最大权重节点。

Question

例如，这是树。

            10
     12           -1
  5       1     1     -2
2   3  10   -9

如何找到具有最大值的节点？

score 1 · Accepted Answer

鉴于上述问题，您需要遍历整个树。见下文证明。

遍历整个树应该是一个相当简单的过程。

证明我们需要遍历整个树：

假设我们能够在不遍历整个树的情况下确定最大值在树的哪一侧。

给定任何具有左侧最大节点的树。调用这个最大值x。

选择右侧的叶节点之一。向其中添加 2 个孩子：x+1和-x-1.

因为x+1-x-1 = 0，添加这些不会改变我们添加它的叶子的总和，因此也不会改变树中任何其他节点的总和。

由于这可以添加到树中的任何叶子上，并且不会影响总和，因此我们需要遍历整个树来确定这是否发生在任何地方。

因此，我们假设我们可以在不遍历整个树的情况下识别最大值在树的哪一侧是不正确的。

因此我们需要遍历整棵树。

score 0 · Accepted Answer

一般情况下，需要遍历整棵树。如果树中的值不受约束（例如，所有非负值，但在您的示例中存在负值），则节点中的值不会告诉您它下面的各个值。

2 回答 2