java - 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，即取右子树并从路径中排除当前节点(以及左子树)

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