algorithm - 应该使用什么类型的遍历来找到二叉树的总和？

Question

以下问题出现在我的导师几年前的一次测试中。他提供了答案，但没有提供令人满意的解释。我用谷歌搜索了这个主题，但没有找到太多。我希望社区可以帮助我理解这个概念。

In order to find the sum of all of the integers in a binary tree, what type of traversal would be used?

(A) breadth-first
(B) depth-first in-order
(C) depth-first post-order
(D) depth-first pre-order

我的导师说答案是 (C) 深度优先后序，但我不明白为什么。看起来他们都会工作。如果您有任何见解，我将不胜感激。

谢谢。

编辑: 我终于明白为什么我的老师认为答案是 (C)。

如果您要在单个语句中编写一个带有 all 加法的求和函数，例如:

    int addup(Node n)
    {
        if (n == nil) return 0;
        return addup(n.left) + n.value + addup(n.right);
    }

无论总和中项的顺序如何，遍历都是后序的。这是因为这两个函数在加法发生之前首先被评估。然而，正如 Keith Randall 在他的回答中所展示的那样，强制执行预排序或有序遍历是微不足道的。

Answer 1

任何遍历顺序都可以，因为 sum 是关联的和对称的。例如，深度优先顺序:

int addup(Node n) {
    if (n == nil) return 0;
    int sum = addup(n.left);
    sum += n.value;
    sum += addup(n.right);
    return sum;
}

所有遍历都允许一个简单的求和实现。