2 个节点之间的最长路径

algorithm java recursion binary-tree

2022-09-05 00:30:55

计算两个节点之间的最长路径。
路径位于拱门中。
方法的签名为：

public static int longestPath(Node n)

在下面的示例二叉树中，它是 4（通过 2-3-13-5-2）。

这就是我现在所拥有的，对于给定的树，它只返回0。

public static int longestPath(Node n) {
    if (n != null) {
        longestPath(n, 0);
    }
    return 0;
}
private static int longestPath(Node n, int prevNodePath) {

    if (n != null && n.getLeftSon() != null && n.getRightSon() != null) {
        int currNodePath = countLeftNodes(n.getLeftSon()) + countRightNodes(n.getRightSon());
        int leftLongestPath = countLeftNodes(n.getLeftSon().getLeftSon()) + countRightNodes(n.getLeftSon().getRightSon());
        int rightLongestPath = countLeftNodes(n.getRightSon().getLeftSon()) + countRightNodes(n.getRightSon().getRightSon());

        int longestPath = currNodePath > leftLongestPath ? currNodePath : leftLongestPath;
        longestPath = longestPath > rightLongestPath ? longestPath : rightLongestPath;

        longestPath(n.getLeftSon(), longestPath);
        longestPath(n.getRightSon(), longestPath);

        return longestPath > prevNodePath ? longestPath : prevNodePath;
    }
    return 0;
}
private static int countLeftNodes(Node n) {
    if (n != null) {
        return 1+ countLeftNodes(n.getLeftSon());
    }
    return 0;
}
private static int countRightNodes(Node n) {
    if (n != null) {
        return 1+ countRightNodes(n.getRightSon());
    }
    return 0;
}

我知道我在某个地方错过了一个关键概念......当我试图跟踪执行流程时，我的大脑会发疯......
我说得对吗，通过找到根，它的左节点和右节点之间的最长路径，然后在它的左节点和右节点上递归，通过它们从上一个方法调用中传递最长的路径，最后（何时？）返回最长的路径，我不确定你如何返回它......

答案 1

也许它同样简单：

public static int longestPath(Node n) {
    if (n != null) {
        return longestPath(n, 0); // forgot return?
    }
    return 0;
}

它比人们乍一看想象的要复杂得多。请考虑以下树：

在这种情况下，根节点甚至不在最长路径中（）。a-7-4-2-5-8-b

因此，您必须执行以下操作：对于每个节点，必须计算以下内容：n

计算左子树中从左子树的根开始的最长路径（称为L)
计算右子树中从右子树的根开始的最长路径（称为R)
计算左子树中的最长路径（不一定从左子树的根开始）（称为l)
计算右子树中的最长路径（不一定从右子树的根开始）（称为r)

然后，决定哪个组合可以最大化路径长度：

L+R+2，即从左子树中的子路径到当前节点，以及从当前节点到右子树中的子路径
l，即只需取左子树并从路径中排除当前节点（以及右子树）
r，即只需取右子树并从路径中排除当前节点（以及左子树）

所以我会做一个小的hack，对于每个节点，不是只返回一个，而是包含.然后，调用方必须根据上述规则决定如何处理此结果。int(L+R+2, l, r)

答案 2

正确的算法是：

从任何节点运行 DFS 以查找最远的叶节点。标记该节点 T。
运行另一个 DFS 以查找距离 T 最远的节点。
您在步骤 2 中找到的路径是树中最长的路径。

这个算法肯定会起作用，你也不仅限于二叉树。我不确定你的算法：

我说得对吗，通过在根，它的左节点和右节点之间找到最长的路径，然后在它的左节点和右节点上递归，通过它们从以前的方法调用中传递最长的路径，最后（当???）返回最长的路径，我不确定你如何返回它......

因为我不明白你到底在描述什么。你能在一个例子上手工工作还是尝试更好地解释它？这样，您可能会更好地帮助理解它是否正确。

您似乎正在尝试递归实现基本上相同的东西，只是为二叉树简化了。但是，对于此问题，您的代码似乎相当复杂。查看此处的讨论，了解更简单的实现。