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

我知道我在某个地方错过了一个关键概念……当我尝试跟踪执行流程时，我的大脑发疯了……
我是这么说的，通过找到根中最长的路径，它的左右节点，然后递归到它的左右节点，传递它们从前一个方法调用的最长路径，最后（当？）返回最长的路径，我我不确定你是怎么回事的……

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 ab 

在这种情况下，根节点甚至不在最长路径中（ 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中找到的路径是树中最长的路径。

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

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

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

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

Answer 3

 public int longestPath() { int[] result = longestPath(root); return result[0] > result[1] ? result[0] : result[1]; } // int[] {self-contained, root-to-leaf} private int[] longestPath(BinaryTreeNode n) { if (n == null) { return new int[] { 0, 0 }; } int[] left = longestPath(n.left); int[] right = longestPath(n.right); return new int[] { Util.max(left[0], right[0], left[1] + right[1] + 1), Util.max(left[1], right[1]) + 1 }; } 

Answer 4

简单实施：

 int maxDepth(Node root) { if(root == null) { return 0; } else { int ldepth = maxDepth(root.left); int rdepth = maxDepth(root.right); return ldepth>rdepth ? ldepth+1 : rdepth+1; } } int longestPath(Node root) { if (root == null) return 0; int ldepth = maxDepth(root.left); int rdepth = maxDepth(root.right); int lLongPath = longestPath(root.left); int rLongPath = longestPath(root.right); return max(ldepth + rdepth + 1, max(lLongPath, rLongPath)); } 

Answer 5

这是我在C ++中的递归解决方案：

 int longest_dis(Node* root) { int height1, height2; if( root==NULL) return 0; if( root->left == NULL ) && ( root->right == NULL ) return 0; height1 = height(root->left); // height(Node* node) returns the height of a tree rooted at node height2 = height(root->right); if( root->left != NULL ) && ( root->right == NULL ) return max(height1+1, longest_dis(root->left) ); if( root->left == NULL ) && ( root->right != NULL ) return max(height2+1, longest_dis(root->right) ); return max(height1+height2+2, longest_dis(root->left), longestdis(root->right) ); } 

Answer 6

我觉得你太复杂了。

想想通过节点n的最长路径并且不会到达n的父节点。 该路径的长度与连接到n的两个子区的高度之间的关系是什么？

搞清楚之后，检查树递归推理如下：

具有根n的子树的最长路径是以下三个中的最长路径：

1. 子树中最长的路径，其根目录为n.left_child
2. 子树中最长的路径，其根目录为n.right_child
3. 最长的路径，通过节点n并且不会到达n的父节点

Answer 7

如果，对于每个节点n ，您的目标是计算这两个数字：

• f（ n ）：以n为根的树中最长路径的长度
• h（ n ）：以n为根的树的高度。

对于每个终端节点（具有null左和右节点的节点），显然f和h都是0。

现在，每个节点n的h是：

• 如果n.left和n.right都为null ， n.right 0
• 如果只有n.left为非null n.left 1 + h（ n.left ）
• 如果只有n.right为非null n.right 1 + h（ n.right ）
• 1 + max（h（ n.left ），h（ n.right ））如果n.left和n.right都是非null

而f（ n ）是：

• 如果n.left和n.right都为null ， n.right 0
• max（f（ n.left ），h（ n ））如果只有n.left是非null
• ?? 如果只有n.right是非null
• ?? 如果n.left和n.right都是非null

（你需要弄清楚是什么取代了两个“??”占位符。有一些选择使这个策略有效。我已亲自测试过。）

然后， longestPath(Node n)只是f（ n ）：

 public class SO3124566 { static class Node { Node left, right; public Node() { this(null, null); } public Node(Node left, Node right) { this.left = left; this.right = right; } } static int h(Node n) { // ... } static int f(Node n) { // ... } public static int longestPath(Node n) { return f(n); } public static void main(String[] args) { { // @phimuemue's example Node n6 = new Node(), n9 = new Node(), a = new Node(), n7 = new Node(n9, a), n4 = new Node(n6, n7), b = new Node(), n8 = new Node(null, b), n5 = new Node(null, n8), n2 = new Node(n4, n5), n3 = new Node(), n1 = new Node(n2, n3); assert(longestPath(n1) == 6); }{ // @Daniel Trebbien's example: http://pastebin.org/360444 Node k = new Node(), j = new Node(k, null), g = new Node(), h = new Node(), f = new Node(g, h), e = new Node(f, null), d = new Node(e, null), c = new Node(d, null), i = new Node(), b = new Node(c, i), a = new Node(j, b); assert(longestPath(a) == 8); } assert(false); // just to make sure that assertions are enabled. // An `AssertionError` is expected on the previous line only. } } 

你应该能够编写f和h的递归实现来使这段代码工作; 然而，这种解决方案非常低效。 其目的只是为了理解计算。

为了提高效率，您可以使用memoization或将其转换为使用堆栈的非递归计算。

Answer 8

好吧，嗯，如果我正确理解你的问题，这是我的解决方案[但在C ++中（对不起）]：

 int h(const Node *root) { if (!root) return 0; else return max(1+h(root->left), 1+h(root->right)); } void longestPath(const Node *root, int &max) { if (!root) return; int current = h(root->left) + h(root->right) + 1; if (current > max) { max = current; } longestPath(root->left, max); longestPath(root->right, max); } int longest() { int max = 0; longestPath(root, max); return max; } 

Answer 9

考虑到@phimuemue示例和@IVlad解决方案，我决定自己检查一下，所以这是我在python中实现的@IVlad解决方案：

 def longestPath(graph,start, path=[]): nodes = {} path=path+[start] for node in graph[start]: if node not in path: deepestNode,maxdepth,maxpath = longestPath(graph,node,path) nodes[node] = (deepestNode,maxdepth,maxpath) maxdepth = -1 deepestNode = start maxpath = [] for k,v in nodes.iteritems(): if v[1] > maxdepth: deepestNode = v[0] maxdepth = v[1] maxpath = v[2] return deepestNode,maxdepth +1,maxpath+[start] if __name__ == '__main__': graph = { '1' : ['2','3'], '2' : ['1','4','5'], '3' : ['1'], '4' : ['2','6','7'], '5' : ['2','8'], '6' : ['4'], '7' : ['4','9','a'], '8' : ['5','b'], '9' : ['7'], 'a' : ['7'], 'b' : ['8'] } """ 1 / \ 2 3 / \ 4 5 / \ \ 6 7 8 / \ \ 9 ab """ deepestNode,maxdepth,maxpath = longestPath(graph,'1') print longestPath(graph, deepestNode) >>> ('9', 6, ['9', '7', '4', '2', '5', '8', 'b'])