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

yiyiyicz

lee1892 发表于 2014-11-23 09:56
真是大手笔呀！前半部分我大致看明白了，可要是一个完全树，这前面的都用不上啊。

对了，所谓完全树是 ...

大概没说清楚，我在这里只是想说清楚树结构，树结构只是图的一种。担任树结构较容易处理，有环，复杂联通，处理就不容易了
当时脑子里主要在想BOM。对于离散制造，BOM都是树形结构

大灰狼1976

偶然翻到时隔多年的帖子，不知道启蒙老师是否还会做出回应。
我看了一下题目，自己思考了一下，先得出以下逻辑，不知有无错误，可以的话请先生指教。
1、树形结构，只有一个连接点的是叶，其他是枝干，很容易判断；
2、把每个叶子距离合并到父节点，然后删除叶子，在父节点记录叶子编号和带来的距离（保留一个或两个叶子信息，下有说明）；
3、叶子合并到父节点时，如果此父节点只有一个分枝（判断它是否只有两个连接就行），则继承叶子信息及距离，如果超过一个分枝，
   则保留两个最长距离的叶子信息及距离，将此两个距离相加后存入临时变量，如果有超过它距离的，把它替换掉
4、上述多个分枝的父节点，如果变成叶子还要合并到它的父节点时，只向父节点传递距离最长的信息（可以是完整路径，也可以只是点信息，因为任意两个点有且仅有一条通路）
5、直到处理至根节点，完成后第3项临时变量的值就是距离最长两点的信息
注：最长距离不一定要通过根节点

micch

大灰狼1976 发表于 2023-8-30 11:12
偶然翻到时隔多年的帖子，不知道启蒙老师是否还会做出回应。
我看了一下题目，自己思考了一下，先得出以下 ...

直到处理至根节点，完成后第3项临时变量的值就是距离最长两点的信息

这一句我理解的是不成立的，因为根节点不是已知的固定的。

整个结构中，每一个节点，都可能是结果中最长距离的根节点。所以如果由叶子向根节点搜索，那么除了叶子本身，要搜索到每一个节点的距离，这个运算量太大了。

大灰狼1976

micch 发表于 2023-8-30 12:52
直到处理至根节点，完成后第3项临时变量的值就是距离最长两点的信息

这一句我理解的是不成立的，因为 ...

层层剪叶最后得到的肯定是根节点。另外，第3项临时变量保存的是每次剪叶后得到的最长距离点信息，和根节点没有关系，判断剪到根节点只是为了判断处理已完成。另外，我最下面一行写了，距离最远的点不一定通过根节点，现在再补充一下，必定是两张叶子之间的距离。

大灰狼1976

另，逐渐简化树复杂度我认为是比较高效的方法。

micch

大灰狼1976 发表于 2023-8-30 14:38
层层剪叶最后得到的肯定是根节点。另外，第3项临时变量保存的是每次剪叶后得到的最长距离点信息，和根节 ...

就是，找到所有叶子，然后向上搜索父节点，然后同一个父节点只记录最长的叶子，然后父节点变为叶子。

然后做下一轮循环搜索，还是所有叶子都计算到父节点的距离，同一个父节点只保留最长的距离，然后删除叶子，父节点变叶子。

这样循环到只剩下一个节点为止。

这样？

大灰狼1976

micch 发表于 2023-8-30 15:19
就是，找到所有叶子，然后向上搜索父节点，然后同一个父节点只记录最长的叶子，然后父节点变为叶子。

...

嗯，我的想法，每个循环都把当前所有叶子（连接数为1）合并到对应父节点，父节点保留叶子信息及距离（如果该父节点上有超过1个叶子，就保留两个最大分枝，其余抛弃；只有1张叶子的直接保留该信息）；
每个循环结束时，当前的叶子全部被剪除，树结构复杂度降低，每二个循环再找新叶子（连接数为1），继续处理，直到结果。
刚才回贴中第3项提到的临时变量，不存在树上任意点的信息内，它只会被新的最大值替换掉，最终留下一个（当然如果考虑可并列的话，也可以保留相同距离长度的多个点信息）

大灰狼1976

做了个简单的过程图示，用来初步验证。
注：其实根节点毫无意义，只要有叶子这个概念就行。

micch

看明白了，逻辑上行得通，接下来就是代码如何写了。

穷举的话，就是一轮一轮循环直到剩下两个节点。用递归也可以按这个逻辑写，就是优化不确定如何优化更合理。

这个贴这么久了，也没人关注了，可惜了