找到任意两个节点之间的最长路径
我有一棵二叉树。我需要编写 Java 递归方法来给出两个节点之间的最长路径。
例如，如果以下树是 7 (7-8-5-13-15-18-16-17)，则最长路径。
http://img294.imageshack.us/img294/130/treeb.jpg
有什么办法可以解决这个问题呢？
（方法： public static int permanentPath(Node n) ）
I have a binary tree. I need to write Java recursive method that will give longest path between two nodes.
For example longest path if following tree is 7 (7-8-5-13-15-18-16-17).
http://img294.imageshack.us/img294/130/treeb.jpg
What's the way to resolve this problem?
(The method: public static int longestPath(Node n) )
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
考虑到这是家庭作业，我会看看 深度优先搜索 和 广度优先搜索。
偏好深度优先
Considering this is homework I'd look at Depth-First search and Breadth-First search.
With a preference for depth-first
首先，您可以编写一个返回树的高度的函数，该高度等于最长路径的长度。
To start with, you can write a function that returns the height of the tree, which is equal to the length of the longest path.
这里有一个线索：
首先，你能解决这个更简单的问题吗？
从整数列表中查找最大值。
其次，只要节点有子节点，就会出现一条新路径。
Here is a clue:
First, can you solve this simpler problem?
Find the max from a list of integers.
Second, a new path occurs whenever a node has children.
另请注意，问题是 NP 完全问题，因此您可能将无法找到多项式算法。
Also note that the problem is NP-complete, so you probably won't be able to find a polynomial algorithm.