应该使用哪种类型的遍历来查找二叉树的和?

Question

下面的问题出现在几年前我的导师给我的一次考试中。他给出了答案，但没有给出令人满意的解释。我在谷歌上搜索了这个话题，但我没有找到太多。我希望社区能帮助我理解这个概念。

为了找到二叉树中所有整数的和，将使用哪种类型的遍历?

(A)宽度优先
(B)深度优先顺序
(C)深度优先后序
(D)深度优先预购

我的老师说答案是(C)深度优先后序，但我不明白为什么。看起来它们都能起作用。如果您能提供一些见解，我将不胜感激。

谢谢。

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

如果你要写一个求和函数，所有的加法都在一个单独的语句中，比如:

    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;
}

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