淘宝2012校招题目，高手们请进

snowboy9859

一颗树上有海量结点，假设在亿这个级别，现在给定任意2个结点（非根结点），请找出他们共同的祖先结点，请在节省空间的前提下，高效查找。
注意：请勿对该树对做任何假设，它不一定是平衡树，也不一定有序。请高手们指教。

wingforce

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

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

unistd

这只能通过类似遍历的方式。
从一个节点出发，回溯到其父节点，然后遍历该父节点的所有字节点，如果找到了另一个节点，则该父节点就是它们共同的父节点，如果找不到，则回溯该父节点的父节点，继续如上查找。

bruceteen

A小狗 一直爬，一直尿，直到爬到根节点
B小狗 一直爬，一直嗅，直到嗅到尿骚味
当然，还可以更快点，就是A和B都撒尿，都嗅，一起爬

zylthinking

A小狗 一直爬，一直尿，直到爬到根节点
B小狗 一直爬，一直嗅，直到嗅到尿骚味
当然，还可以更快点，就是 ...
bruceteen 发表于 2011-09-22 08:18

好办法， 但如何节省空间呢？

mirnshi

好办法， 但如何节省空间呢？
zylthinking 发表于 2011-09-22 10:18

这个不需要额外的空间吧？
将节点按照固定尺寸内存对齐，每个指针的后几位就可以保存访问状态了。轨迹有了，相互比较一下就行了。

zylthinking

这个不需要额外的空间吧？
将节点按照固定尺寸内存对齐，每个指针的后几位就可以保存访问状态了。轨迹 ...
mirnshi 发表于 2011-09-22 10:26

这样就是对节点自身地址做假设了； 而且， 即便如此， 仍需要第2遍遍历将状态恢复原始状态

zylthinking

倒是想了个办法， 就是有点猥琐， 向上遍历时， 将兄弟节点的地址+1, 这样， 兄弟节点也到达时， 会发现自己的地址既不是 left_child, 也不是right_child, 则找到共同父节点； 然后各自从自身开始重新遍历直到共同父节点， 这一次是修正之前的修改， 将兄弟节点地址 -1; 在然后从共同父节点一直向上， 直到第一次遍历时到达的最高节点， 同样是修正之前的修改。

优点是空间O(1); 缺点是2次遍历， 每个节点都会做写操作，不够高效， 而且是独占式操作， 在未恢复修改前， 树结构其实被破坏了。

mirnshi

这样就是对节点自身地址做假设了； 而且， 即便如此， 仍需要第2遍遍历将状态恢复原始状态
zylthinking 发表于 2011-09-22 10:34

内存地址对齐，其实不过分，很多情况下为了提高内存访问效率，都是要对齐的。与树的结构/内容不冲突。
并没有改变树结构，恢复原始状态是什么意思？

zylthinking

内存地址对齐，其实不过分，很多情况下为了提高内存访问效率，都是要对齐的。与树的结构/内容不冲突。
...
mirnshi 发表于 2011-09-22 11:14

问题是 ”请勿对该树对做任何假设“ ， 我说的恢复是状态的恢复， 你总不能这一次修改了状态， 找到后就撒手不管了； 下一次再查找你还怎么修改状态呢， 上一次的状态残留下了