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

zylthinking

1. 足够大是多大？？？
2. 题目要求可是“节省空间的前提下”

fanronghua

那也简单啊
long nodearray[]; //可以改用链表

while (node1->parent <> root ) || (node2->parent <> root)
{
// 查找 node1->parent 是否在链表内
nodearray【i++】 := node1->parent;

// 查找 node2->parent 是否在链表内
nodearray【i++】 := node2->parent;

node1 = node1->parent;
node2 = node2->parent;

}

zylthinking

唉， 你仔细读帖子看看其他人的方法吧

fanronghua

你们现在要比较节点的深度，这个是不可能的事情，有的节点可能是直接就第2亿个，很深。
我现在的办法，就是把已知的两个节点向上查找，没一个步，多把自己的父节点记录下来，
谁先查找到，与已经记录的节点地址相同，那这个节点就是想通的节点。

我们假设最好的情况，和最差的情况，
最好的情况，就是他们的父节点就是相同，那我只要循环一次就可以了。
最差的情况，就是他们root节点是相同的，那他们一定要循环2亿次。
                  那这个链表就有2亿个节点记录着。

fanronghua

你如果想先求深度的话，假如深度为 2亿，你第一步就死掉了。

mirnshi

你们现在要比较节点的深度，这个是不可能的事情，有的节点可能是直接就第2亿个，很深。
我现在的办法，就是 ...
fanronghua 发表于 2011-09-22 15:40

算法有问题吧，还是没有阐述清楚？

fanronghua

0.开辟一个链表头head。
1.建立两个指针 node1 node2
2.移动node1= node1->parent; 查找 node1 是否在链表内，如果有，找到了，退出，如果没有，插入链表.
   如果为根节点，不做插入动作。
3.nod2做（1）相同的动作。
4.重复 （2）.

zylthinking

你们现在要比较节点的深度，这个是不可能的事情，有的节点可能是直接就第2亿个，很深。
我现在的办法，就是 ...
fanronghua 发表于 2011-09-22 15:40

如果说极限， 那么如果共同父节点是根结点， 根结点右分支只有右分支， 左分支只有左分支， 已知节点分别左分支最后一个及右分支最后一个， 你的办法需要占用多大空间呢？？？
其实你这个办法就是小狗撒尿算法的一个变形； 而且， 它还不用你那样在链表中一遍遍搜索是否已经命中另一个节点记录的父节点， 而且， 它还不用占用那么大的空间；

至于你说的可能在找到共同父节点后， 仍未搜索到根结点的情况； 小狗撒尿算法也一样能做到的： 就是两支狗同时撒尿同时嗅那种方法。
和比较深度相比， 这个算是优点； 但这个优点也只能在已知2节点在树上纵向及横向上都比较临近时更有意义些。

zylthinking

用你的步骤简化的说， 就是：

0.开辟一个链表头head。
1.建立两个指针 node1 node2
2.移动node1= node1->parent; 查找 node1 是否在链表内－－－》每走一步查找一次， 性能糟糕，如果有，找到了，退出，如果没有，插入链表－－－》内存占用.
   如果为根节点，不做插入动作。
3.nod2做（1）相同的动作。
4.重复 （2）
fanronghua 发表于 2011-09-22 15:57

所以， 即便不和算深度比， 和小狗撒尿来比， 只有一个优点， 就是不用第二遍遍历， 因为你将状态记录在了链表里， 所以不用走第二遍重置状态； 但和纪录在节点内部方法相比， 似乎不及

zylthinking

你如果想先求深度的话，假如深度为 2亿，你第一步就死掉了。
fanronghua 发表于 2011-09-22 15:48

如果深度2亿， 其他方法至少可以活着计算， 就算花了几百年， 也不会死掉； 而你的照样是2亿， 还背着一个2亿长度的链表， 就算是单链表， 一个存储的节点地址加一个next 指针， 8字节 * 2亿， 是多少？？？