2个节点之间的最长路径

Question

计算两个节点之间的最长路径.
路径是拱形的.
签名方法是:

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;
}

我明白我在某个地方错过了一个关键概念......当我尝试跟踪执行流程时,我的大脑变得疯狂......
我是通过找到根,它的左右节点之间的最长路径来说的.然后递归它的左右节点传递它们从前一个方法调用的最长路径,最后(当？)返回最长的路径,我不确定你如何返回它...

Answer 1

也许它就是这么简单:

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

它比一见钟情更复杂.考虑以下树:

      1
     / \
    2   3
   / \
  4   5
 / \   \
6   7   8
   / \   \
  9   a   b

在这种情况下,根节点甚至不在最长路径(a-7-4-2-5-8-b)中.

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

• 从左子树的根开始计算左子树中的最长路径(被调用L)
• 从右子树的根开始计算右子树中的最长路径(称为R)
• 计算左子树中的最长路径(不一定以左子树的根开始)(被调用l)
• 计算右子树中最长的路径(不一定以右子树的根开头)(称为r)

然后,决定哪个组合最大化路径长度:

• L+R+2,即从左子树中的子路径到当前节点,从当前节点到右子树中的子路径
• l,即只取左边的子树并从路径中排除当前节点(从而右边的子树)
• r,即只取正确的子树并从路径中排除当前节点(从而保留左子树)

所以我会做一点点破解,并且每个节点都不会只返回一个int,而是包含三个整数(L+R+2, l, r).然后,呼叫者必须根据上述规则决定如何处理此结果.

Answer 2

一个正确的算法是:

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

这个算法肯定会起作用,你也不仅限于二叉树.我不确定你的算法:

我是这么说的,通过找到根中的最长路径,它的左右节点然后递归到它的左右节点,从它们传递前一个方法调用的最长路径,最后(当???)返回最长的路径,我不确定你是怎么回事的......

因为我不明白你究竟在描述什么.你可以手工制作一个例子或尝试更好地解释它吗？这样你可以更好地帮助理解它是否正确.

您似乎正在尝试递归实现基本相同的事情,只是为二叉树简化.但是,对于这个问题,您的代码似乎相当复杂 请查看此处的讨论,以获得更简单的实现.