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

davidfoxhu

这个树的结构咋定义的呢，N叉树？

zylthinking

我说你这个办法不是最优的方案。在我 （1）的例子里，我只要走一步就可以得到结果，
你要走两亿 ...
fanronghua 发表于 2011-09-22 16:21

小狗撒尿两只小狗同时撒尿同时嗅， 你以为需要几步就能得到结果？？？

fanronghua

小狗撒尿两只小狗同时撒尿同时嗅， 你以为需要几步就能得到结果？？？
zylthinking 发表于 2011-09-22 16:32

    你说的没有错，在最优的情况下，我只需要一步就可以啦。

zylthinking

你说的没有错，在最优的情况下，我只需要一步就可以啦。
fanronghua 发表于 2011-09-22 16:37

所以， 你的方法和小狗撒尿相比， 没有明显优点；缺点却是不容忽视的
而小狗撒尿和计算深度比， 看已知节点分布情况， 各有优缺点。

fanronghua

所以， 你的方法和小狗撒尿相比， 没有明显优点；
而小狗撒尿和计算深度比， 看已知节点分布情况， 各 ...
zylthinking 发表于 2011-09-22 16:39

    在这种未知树的情况下，预想去做计算，多有可能导致死循环（可能计算的结果巨大的情况下），只有直接去做查找比较动作，才是最优的。

zylthinking

在这种未知树的情况下，预想去做计算，多有可能导致死循环（可能计算的结果巨大的情况下），只有 ...
fanronghua 发表于 2011-09-22 16:42

不知你在说什么， 你先别和计算深度的哪个方法比了， 先和小狗撒尿的算法比吧。

0， 保存A 为saveA, B为saveB
1。 两节点直接比， 相等退出
2。 节点 tmp = A->parent; if(tmp->left != A && tmp->right != A) 则tmp 为共同父节点； 否则 if(tmp->left == A) {tmp->right +=1;}else{tmp->left +=1;}
3。 和2相同， 将A替换成B
4.   如果找到共同节点， 从 saveA开始直到tmp, 将步骤2中做的 +1 进行反操作； 从saveB到tmp 将步骤3中做的＋1进行反操作; 而后转到6
5. 如果没有找到共同节点， 则A = A->parent, B = B->parent, 转到2；     
6， 返回tmp

fanronghua

不知你在说什么， 你先别和计算深度的哪个方法比了， 先和小狗撒尿的算法比吧。

0， 保存A 为saveA, ...
zylthinking 发表于 2011-09-22 16:52

    left,right ?? 你怎么知道他是 二叉树？ 他有可能是 N个叶子的树啊！天哪！ 有可能是上亿个啊。

zylthinking

如果是多叉， 则将所有 tmp->ptr != A 的所有 ptr 都 +1, 不影响讨论；

fanronghua

如果是多叉， 则将所有 tmp->ptr != A 的所有 ptr 都 +1, 不影响讨论；
zylthinking 发表于 2011-09-22 17:03

    上亿个怎么办？ 你又陷入2亿个循环了，多说了，不能做假设的。

zylthinking

上亿个怎么办？ 你又陷入2亿个循环了，多说了，不能做假设的。
fanronghua 发表于 2011-09-22 17:08

你这就是抬杠了。。。。。。。那我同意你的是最好的， 你的不会陷入2亿个循环？？ 看这个
        o
       / \
     A   X
      \
       ...(2亿个)
         \
          B