java - 获取树状结构的最长子路径

Question

我正在编写一个函数来帮助我计算树状数据结构的最长子路径。到目前为止，我所写的是使用递归方法“挖掘”到每个子分支——基本上是深度优先搜索。我对 tree 没有太多控制，它只是一个 Map，其中每个键都是一个节点，每个键的值是一个节点列表，这些节点是关键点到。

例如树 map 可以有:

"start" => ["1"]
"1" => ["2"]
"2" => ["3", "4"]
"3" => ["5"]
"4" => ["end"]
"5" => ["end"]

我相信我在下面编写的代码通过使用树中所有子路径的长度填充 subLengths 列表来解决我的问题。接下来我要做的就是减少 subLengths 以获得最大长度。

private void calculateAllSubPathLengths(String start, Map<String, List<String>> tree, int pathLength, List<Integer> subLengths){
    pathLength++;
    for(String connectedNode: tree.get(start)) {
        if(connectedNode.equals("end")) {
            subLengths.add(pathLength);
            return;
        }

        calculateAllSubPathLengths(connectedNode, tree, pathLength, subLengths);
    }
}

我这样称呼这个函数:

int pathLength = 0;
List<Integer> subLengths = new ArrayList<>();
calculateAllSubPathLengths("start", tree, pathLength, subLengths);
// Get max from the subLengths list and move on with the rest of my logic

我对 tree 映射内部的数据没有太多控制权，它没有像二叉树那样的任何传统树类属性。树中的节点可以有很多分支，并且它可以嵌套很多层。但是，考虑到我的问题领域，这是极不可能的。但是，我想确保我的代码能够处理更复杂的树，以防将来它们变得更有可能。

我发布这个问题是因为我的直觉是我做的不正确。我的问题是:

1. 有什么方法可以避免使用 subLengths 列表吗？
2. 有没有办法将这个递归函数转换成交互式函数？如果没有，我可能会添加某种条件，一旦我们达到某个“深度”就停止该功能。
3. 我是否违反了任何其他递归“最佳实践”？

Answer 1

您的代码有一些 undefined variable :links 应该是 tree 并且 subPathLengths 应该是 subLengths。

除这些问题外，代码似乎适用于这种情况(最长路径为 5)，因此我将解决您的问题并指出您的代码失败的情况。自始至终，我假设您的树实际上是一棵树(即非循环树)。

1. 这似乎是一种可接受的方法。您的函数名称是 calculateAllSubPathLengths，因此该列表似乎适合存储所有路径。如果您只想要最长的(看起来是这种情况)，请为您的函数添加一个返回值并将运行最好的作为参数而不是 subLengths 传递。您还可以使用单元素 int[] best“通过引用”传递，这避免了某些比较但会导致语义问题。

2. 当然，您可以使用一个显式堆栈迭代地执行此操作，该堆栈包含您通常传递给递归函数的参数。这是一种方法:

   class Pair<K, V> {
       K first;
       V second;
   
       public Pair(K first, V second) {
           this.first = first;
           this.second = second;
       }
   }
   
   private static int longestPath(HashMap<String, List<String>> tree) {
       Stack<Pair<String, Integer>> stack = new Stack<>();
       stack.push(new Pair<String, Integer>("start", 0));
       int best = 0;
   
       while (!stack.isEmpty()) {
           Pair<String, Integer> current = stack.pop();
   
           if (current.first.equals("end")) {
               best = Math.max(current.second, best);
           }
           else {
               for (String child : tree.get(current.first)) {
                   stack.push(
                       new Pair<String, Integer>(child, current.second + 1)
                   );
               }
           }
       }
   
       return best;
   }
   

   Try it!

3. 这里有一些针对递归函数的“最佳实践”建议:

   • 您的实现会强制调用者负责许多本质上对递归函数而言是局部的变量。编写一个辅助方法来封装这些变量，为调用者提供一个干净的 calculateAllSubPathLengths(tree); 选项。

   • 在函数顶部增加 pathLength 并测试 connectedNode.equals("end") 似乎违反直觉将每个节点或状态视为单个实体.你的函数会问，“当前节点的这个邻居是终点吗？”和“增加路径，然后分析当前节点”当问“这个节点是终点吗？”似乎更语义化时。和“分析当前节点，然后在我们移动到邻居时增加路径”。这也具有逻辑意义；例如，如果开始节点是结束节点，您的代码将失败。

   将这些项目放在一起，这是一个可能的重构:

   private static int longestPath(Map<String, List<String>> tree) {
       return longestPath("start", tree, 0, 0);
   }
   
   private static int longestPath(
       String current, Map<String, List<String>> tree, 
       int pathLength, int best
   ) {
       if (current.equals("end")) {
           return Math.max(pathLength, best);
       }
   
       for (String child : tree.get(current)) {
           best = Math.max(
               best, longestPath(child, tree, pathLength + 1, best)
           );
       }
   
       return best;
   }
   

   Try it!

   即使在这里，也有很多需要改进和推广的地方。例如，硬编码 “start” 和 “end” 状态会破坏可重用性。