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

Question

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

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

(A) 广度优先
(B) 深度优先顺序
(C) 深度优先后序
(D) 深度优先前序

我的导师说答案是（C）深度优先后序，但我不明白为什么。似乎他们都会工作。我将不胜感激您可能拥有的任何见解。

谢谢。

编辑：我终于明白了为什么我的导师认为答案是（C）。

如果您要在单个语句中编写一个带有加法的 sum 函数，例如：

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

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

score 3 · Accepted Answer

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

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

所有的遍历都承认一个简单的求和实现。

1 回答 1