java - 2个节点之间的最长路径

计算两个节点之间的最长路径。
路径在拱门中。
方法的签名是:

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

我知道我在某个地方缺少关键概念...当我尝试跟踪执行流程时，我的大脑发疯了...
我是说对了吗，是通过找到根，左节点和右节点之间的最长路径，然后在其左节点和右节点上递归，从而将先前方法调用中的最长路径传递给它们，最后(何时？)返回最长路径，我不确定如何退还...

最佳答案

也许就这么简单:

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)的三整数。然后，调用者必须根据上述规则决定如何处理此结果。