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 st开发者_开发问答atic int longestPath(Node n) )
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.
Also note that the problem is NP-complete, so you probably won't be able to find a polynomial algorithm.
精彩评论