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

zylthinking

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

这个应该比小狗撒尿的算法要好； 但还可以改进

3，比较节点的深度，移动较深得那个节点得游标指向其父节点   －－－－－－－－－－》较深的节点直接上移， 直到两个游标深度相同
4，比较2个游标，如果指向同一节点，则该节点为共同祖先，否则回到第3步 －－－－－－－》各自均上移一个节点， 再次执行第4步

fender0107401

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

   

snowboy9859

回复 2# wingforce


    谢谢你个分析，能不能给个代码或者是伪代码？

snowboy9859

回复 4# bruceteen


    您的比喻很生动，实现起来未必很简单

snowboy9859

这个应该比小狗撒尿的算法要好； 但还可以改进

3，比较节点的深度，移动较深得那个节点得游标指向其 ...
zylthinking 发表于 2011-09-22 12:13

    借用你的一句话，请授我以鱼， 不要授我以渔

zylthinking

借用你的一句话，请授我以鱼， 不要授我以渔
snowboy9859 发表于 2011-09-22 14:33

我要是卖渔具的， 就写请去看什么书什么章节了
之所以说它略好， 小狗撒尿算法找不到只需要一次遍历的办法， 至少我还没有想到； 而如果考虑小狗撒尿的第二遍遍历的话， 两者节点访问次数差不多不相上下； 后者写次数要少， 不是独占性操作

rainman00001

看看

fanronghua

简单的不得了。
long node1addr[MAX]  ;
long node2addr[MAX]  ;

while (node1.parent <> root)
{
    node1addr[i++] =  node1.parent;
   node1 = node1.parent;
}

while (node2.parent <> root)
{
    node2addr[i++] =  node2.parent;
   node2 = node1.parent;
}

//反排列 node1addr ,node2addr

for (i =0;i < MAX ;i ++)
{
if (node1addr[i] <> node2addr[i])
{
//就是这个节点
}
}

zylthinking

简单的不得了。
long node1addr[MAX]  ;
long node2addr[MAX]  ;

while (node1.parent  root)
{
    ...
fanronghua 发表于 2011-09-22 15:05

请问 MAX = ???

fanronghua

足够大，不就可以了