如何遍历树以查找最低值

Question

给定一个图形，从指定节点开始（例如橙色），如何获得最低值的叶节点（例如绿色）？

它不是二进制的，因此一个节点可能有数百个子节点。不保证儿童的价值低于其父母。

有没有比简单地遍历每个分支更好的方法？如果没有，那么我们可以将所有叶子收集到一个集合中以找到最低值的叶子。

不幸的是，这将是非常昂贵的。

Answer 1

如果树上没有特定属性，则树遍历是执行此类操作的方法。 这个伪代码描述了一种可行的方法：

find_min(node):
    result = node.value
    for each child of node:
        child_min = find_min(child)
        if child_min < result:
            result = child_min
    return result

但最终，你将不得不穿过你树的所有分支。那是因为要找到min，你必须遍历树的所有节点，然后遍历它。在一般情况下没有更快的方法，因为它在O(n)中运行，n是树中的节点数。 它也是最简单的方法，其他方法会更复杂，因此更容易出错。