algorithm - 一种算法，它在树中沿着每一层的最大节点值找到一条路径

Question

我正在寻找一种算法，该算法可以在树中沿着每个级别的最大节点值找到一条路径。下图说明了这个问题:

如果一个关卡上的所有节点都具有唯一值，那么这个问题就很简单了。但是，如果一个级别上有重复值，那么我(假设我)需要某种前瞻性。如示例中所示，如果有平局，则选择允许在下一个级别中获得更高值的路径。走上“极端”之路

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 0

会在路径上被选择

1 -> 2 -> 3 -> 4 -> 5 -> 5 -> 99

一旦只有一条可能路径，算法可能会退出。

直到现在，我天真的解决方案一直是找到所有可能的路径，然后逐层比较它们，这适用于我正在处理的(小)树，但我想找到一个“合适的”解决方案.

我很确定这个算法已经实现了，但是，我发现很难找到合适的搜索词。有人知道这个问题的解决方案吗？

Answer 1

您可以从根开始并维护候选列表。最初，根是列表中的唯一元素。在每次迭代中，您可以查看当前候选人的所有 child ，并将具有最大值的 child 放入新的候选人列表中(即，每次迭代都降低一级)。

每个节点最多被访问一次，所以这个解决方案具有线性时间复杂度。