来个难度高点的：用最快的方法找出一个树内距离最远的两个节点间的距离

lee1892

没有技术分的题目，大家会参与吗？欢迎跟贴报名呀~

参与方式：
1、11月21日、22日两天中回帖答案，请不要在此之前或之后提交答案，以免参考他人答题办法之嫌。
2、没有最快，只有更快。大家一起来比较谁的速度最快，有分的捧个分场，有花的捧个花场。
参与的人既是答题者也是评分者！

---

题目：
在一个树数据结构中，找出相距最远的两个节点的距离（由一个节点到另一个节点所经过的不重复的边的数量）。

条件：
1、节点数量 N，0<N<=10000
2、输入，一个以分号和逗号相隔的字符串（无多余的任何其它字符），结构如下
    a、第一个分号左侧为树中节点的数量 N
    b、其余分号分隔的字符串，以逗号分隔的相连接的两个节点编号（节点编号为自 1 始至 N 止，编号对无重复）
3、输出，距离值

注：所谓树，对其中任一节点，仅有一个父节点，或有数个子节点，而与兄弟节点并不相连。所以不存在 1<->2, 1<->3, 2<->3 这样的可能。

例子：
输入
4;1,2;1,3;2,4
输出
3

要求：
编写函数：
Public Function LongestPath(ByVal strTree As String) As Long
...
End Function

有需要外部变量、函数过程、自定义类型等等，请都写为Private。

直接提交代码或是附件。


随机题目生成代码，供参考用：

1. Function RandomTree$()
   
2.     Dim nCnt%, i%, nInd%, nLast%, nChildNumMax%
   
3.     nCnt = Int(Rnd * 10000) + 1
   
4.     nChildNumMax = 10
   
5.     nInd = 1: nLast = 1: RandomTree = CStr(nCnt)
   
6.     Do
   
7.         For i = 1 To Int(Rnd * nChildNumMax) + 1
   
8.             nLast = nLast + 1
   
9.             If nLast > nCnt Then Exit Do
   
10.             RandomTree = RandomTree & ";" & CStr(nInd) & "," & CStr(nLast)
    
11.         Next
    
12.         nInd = nInd + 1
    
13.     Loop
    
14. End Function

复制代码

lee1892

这个没有人吗？难道是因为没人给技术分？

wcymiss

楼主申请做竞赛区版主吧。我顶你:-D

cl63519

代码不会写，思路倒是有了，
左深度+右深度。

题目的大概意思是这棵树吧：

         1
      /     \
     2       3
    /
   4

1的左深度为2，
右深度为1，、
所以为2+1 = 3 ?

lee1892

有人参与讨论，我就发提示哈。

1，节点处分支数量不定

lee1892

2，最长路经是否必然经过根节点？

lee1892

3、距离根节点最远的两个节点间是否距离最远？

lee1892

修改了一下题目，加了个注，加了几个括号......

4、谁是根节点？

wcymiss

提个问题，顺便顶顶贴：

“1”是否一定是最高顶点？父节点是否一定比子节点的数字小？

lee1892

wcymiss 发表于 2014-11-12 20:08
提个问题，顺便顶顶贴：

“1”是否一定是最高顶点？父节点是否一定比子节点的数字小？

见提示4，呵呵～
就知道会有人有这问题～