开发者

Find the longest path between any two nodes

开发者 https://www.devze.com 2023-01-05 06:40 出处:网络
I have a binary tree. I need to write Java recursive method that will give longest path between two nodes.

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.

0

精彩评论

暂无评论...
验证码 换一张
取 消