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

Question

例如，这是树。

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

如何找到最大值的节点？

Answer 1

鉴于上述问题，您需要遍历整棵树。请参阅下面的证明。

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

证明我们需要遍历整棵树:

假设我们能够在不遍历整棵树的情况下识别出最大值在树的哪一侧。

给定任意一棵最大节点在左边的树。称此最大值为 x。

选择右侧的叶节点之一。向其中添加 2 个 child :x+1 和 -x-1。

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

因为这可以添加到树中的任何叶子，并且它不会影响总和，所以我们需要遍历整个树以找出是否在任何地方发生这种情况。

因此，我们假设无需遍历整棵树就可以确定最大值在树的哪一侧是不正确的。

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