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

Question

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

例如 tree 地图可以有：

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

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

有什么办法可以避免使用 subLengths 列表吗？
有没有办法将这个递归函数转换成交互函数？如果没有，我可能会添加某种条件，一旦我们达到某个 "depth".
我是否违反了任何其他递归 "best-practices"？

Answer 1

您的代码有一些未定义的变量：links 应该是 tree 并且 subPathLengths 应该是 subLengths。

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

这似乎是一种可以接受的方法。您的函数名称是 calculateAllSubPathLengths，因此该列表似乎适合存储所有路径。如果您只想要最长的（似乎是这种情况），请为您的函数添加一个 return 值并将运行作为参数而不是 subLengths 作为参数传递。您还可以使用单个元素 int[] best 传递 "by reference"，这避免了一些比较但会导致语义问题。

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

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!

这里有一些 "best practices" 递归函数的建议：
- 您的实现强制调用者负责许多变量，这些变量本质上是递归函数的局部变量。编写一个辅助方法来封装这些变量，为调用者提供一个干净的 calculateAllSubPathLengths(tree); 选项。
- 在函数顶部递增 pathLength 并测试 connectedNode.equals("end") 似乎违反直觉将每个节点或状态视为单个实体。当询问 [=68=] 和 "analyze the current node, then increase the path as we move to a neighbor" 似乎更具语义时，您的函数会询问 "is this neighbor of the current node the end?" 和 "increase the path, then analyze the current node"。这也具有逻辑意义；例如，如果起始节点是结束节点，您的代码将失败。
将这些项目放在一起，这是一个可能的重构：
```
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" 状态会破坏可重用性。

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

Getting the longest subpath of a tree-like structure

java

recursion

depth-first-search