论坛徽章:: 0

1楼 [报告]

发表于 2011-09-22 05:37 |显示全部楼层

1，如果树的节点不包含深度信息，那么通过递归回到根节点求出深度信息
2，建立2个游标，分别指向2个节点
3，比较节点的深度，移动较深得那个节点得游标指向其父节点
4，比较2个游标，如果指向同一节点，则该节点为共同祖先，否则回到第3步

如果深度信息为已知，算法复杂度为O(n)，n是2个节点之间得距离
如果深度信息为未知，算法复杂度为O(N)，n是2个节点得深度和

wingforce

白手起家

论坛徽章:: 0

2楼 [报告]

发表于 2011-09-23 16:25 |显示全部楼层

本帖最后由 wingforce 于 2011-09-23 16:37 编辑

在“不对树的结构做任何假设的情况下”，所谓最差情况的2亿循环是根本没法避免的。
没有深度信息，或排序性，或平衡性，又或者类似线索树的复杂结构，这个问题最终会简化为

“求2个单向链表的交点”

- 这个也可以同时解决和解释前面有人说的，如果2个结点没有共同祖先，在这个模型下就是2条不相交的单向链表
- 这和树是2叉还是n叉都没有关系

而这个问题的时间复杂度无论如何不会低于O(n + m), n和m分别是2个单向链表到他们交点的距离，n + m最差情况就是树的结点总数。
每个结点上保存深度也好，小狗爬爬也好，或者是把其中一条路线存储起来查询也好，本质来说空间复杂度都是O（n），n是选取的那条路径的长度，最差情况就是树的结点总数。
每个结点保存深度和小狗爬都是额外信息保存在结点内部，其实依然额外消耗的空间

存储起来查询，要解决的问题是查询加速，无论hash还是什么树，都会很难做到O（1）时间获得查询结果。
各种查询树的查询复杂度都不能超过O（logn），这样算法的时间复杂度是O（n × logn）

hash看起来很美，理论上是O（1），实际上由于hash存在冲突的情况，比较难以分析。理想情况的总复杂度是O（n）。实践中，因为前面说的存在冲突情况，会大于O（n）。如果我没记错，为解决冲突，实际上会是n的一个大于1，小于2的幂次，大概这样O（1 ^ 1.0xxx）

所以，如果需要最理想的O（1）空间复杂度，以及和上面所有方法一样的O（n）时间复杂度
先计算2个结点的深度，再使用游标保存当前所指向的结点，才可以“不做任何假设”的，“最优”的空间和时间复杂度解决这个问题。
因为计算2个结点深度的时间复杂度依然是O（n+m），再根据深度求交点的步骤的复杂度也是O（n+m）
所有他们的和没有变，O（n+m）