沿着每个级别的最大节点值在树中查找路径的算法

Question

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

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

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

将在路径上选择

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

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

到目前为止，我天真的解决方案是找到所有可能的路径，然后逐级比较它们，这适用于我正在处理的（小）树，但我想找到一个“正确的”解决方案。

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

Answer 1

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

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

Answer 2

这是一个可能的实现（未经测试）

假设基于节点的树结构如下：

internal class Node
{
  int Value ;
  List<Node> Children ;
}

主要程序

// Initialize the best path and call the Seek procedure
List<Node> BestPath = SeekBestSubPath(TheRootNode) 

递归函数

private List<Node> SeekBestSubPath(Node CurrentNode)
{
  // identify one or more children with max value   
  List<Node> BestChildrenNodes = null ;
  int Max = int.MinValue ;
  for (int i=0;i<CurrentNode.Children.Count;i++)
    if (CurrentNode.Children[i].Value > Max) 
      BestChildrenNodes=new List<Node>() { CurrentNode.Children[i] } ;
    else if (CurrentNode.Children[i].Value == Max)
      BestChildrenNodes.Add(CurrentNode.Children[i]) ;

  // Process BestChildrenNodes
  List<Nodes> result = new List<Node>() ;
  for (int i=0;i<BestChildrenNodes.Count;i++)
  { // search the best sub path for each child and keep the best one among all  
    List<Node> ChildBestSubPath = SeekBestSubPath(BestChildrenNodes[i]) ;
    if (PathComparator(ChildBestSubPath,MaxPath)>1) result=ChildBestSubPath ;
  }
  result.Insert(0,CurrentNode) ;
  return result ;
}

比较 2 个子路径

private PathComparator(List<Node> Path1,List<Node> Path2)
{ returns 0:equality, 1:Path1>Path2, -1:Path1<Path2
  int result = 0
  for (int i=0;i<Math.Min(Path1.Length,Path2.length) && result=0;i++)
     result=Math.Sign((Path1[i].Value).CompareTo(Path2[i].Value));
  if (result==0) result=Math.Sign(((Path1[i].Count).CompareTo(Path2[i].Count)); 
  return result ;
}