关于在二叉树中求两个节点的最低祖先(lowest ancestor)的算法,请大家多多指教。

hellhell

原帖由 lenovo 于 2005-11-17 18:12 发表
分别找到root节点到这两个节点的路径，
最后一个相同的节点就是它们最近的共同祖先。

我觉得这个办法不错

yaomingwei_ren

原帖由 lenovo 于 2005-11-17 18:12 发表
分别找到root节点到这两个节点的路径，
最后一个相同的节点就是它们最近的共同祖先。

如果是无序的最坏情况需要遍历整个树将近两次，时间复杂度不是很好

yarco2

一次bianli就够了...

stack;

travel(tree, pa, pb)
{
if (tree==NULL) return;
if (tree==pa) {
   save_stack_to(stack, pa_stack);
} else if (tree==pb) {
   save_stack_to(stack, pb_stack);
}
if (tree->left != NULL) {
   push(tree->key, stack);
   travel(tree->left, pa, pb);
}
if (tree->right!=NULL) {
   push(tree->key, stack);
   travel(tree->right, pa, pb);
}
pop(stack);
}

diff_stack(pa_stack, pb_stack)
{
// ...
}
比较下pa_stack和pb_stack估计就差不多了

另: 题目不错. 希望LZ多发这种贴子. 增加大家经验zhi.

[ 本帖最后由 yarco2 于 2005-11-18 04:54 编辑 ]

lisp

我把大家给出的方法归纳了一下：
win_hate 的第一种方法和lenovo的方法都需要两次遍历二叉树；yarco2将其改进为一次遍历即可。
而win_hate提出的第二种方法空间效率和时间效率都最好，但实现的难度好像很大，写代码很复杂。

win_hate

我的第二个 proposal 的确不够简洁，但应该还是能实现的。
设计一个主递归函数： double_find (root, a, b, x); 中序遍历一棵树

其返回值 S00, S01, S10, S11 分别表示找不到， 找到了 b， 找到了 a, 找到 a, b
x 为节点指针的指针，如果找到所需的 parent 节点，则存放在 *x 中。 x 也可以换为一个全局变量。

再设计一个 single_find (root, a) 在找到其中一个的情况下找另一个。

代码类似这样

1. 
   
2. #define S00 0x0;
   
3. #define S01 0x1;
   
4. #define S10 0x2;
   
5. #define S11 0x3;
   
6. 
   
7. double_find (root, a, b, x)
   
8. {
   
9.         int rv, rv2;
   
10. 
    
11.         if (root == NULL)
    
12.                 return S00;
    
13. 
    
14.         if (root == a) {
    
15.                 rv = single_find (root->l, b)
    
16.                 if (rv == 1) {
    
17.                         *x = root;
    
18.                         return S11;
    
19.                 } else {
    
20.                         rv = single_find (root->r, b);
    
21.                         if (rv == 1) {
    
22.                                 *x = root;
    
23.                                 return S11;
    
24.                         } else
    
25.                                 return  S10;
    
26.                 }
    
27.         }
    
28.        
    
29.         if (root == b) {
    
30.         ......
    
31.         }
    
32. 
    
33.         rv = double_find (root->l, a, b, x)
    
34.         switch (rv) {
    
35.                 case S11:
    
36.                         return S11;
    
37.                         break;
    
38.                 case S10:
    
39.                         rv2 = single_find (root->r, b);
    
40.                         if (rv2 == 1) {
    
41.                                 *x = root;
    
42.                                 return S11;
    
43.                         } else
    
44.                                 return S10;
    
45.                         break;
    
46.                 case S01:
    
47.                         ....
    
48.                 case S00:
    
49.                         rv2 = double_find (root->r, a, b, x);
    
50.                         return rv2;       
    
51.                         break;
    
52.                 default:
    
53.         }
    
54.                
    
55. }
    

复制代码

由于并没有写出完整代码，所以无法调试，如果有 bug，请指出。谢谢。