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

lisp

最近遇到这样一道题，下来做了一下。
我的想法是这样的：这个题目的实质就是找到二叉树中的一个节点，以该节点，假定为root，为根的树同时包含这两个目标节点，并且以root->pLeft 和 root->pRight为根的树都不同时包含这两个节点，root 即为所求，算法复杂度为n+(n-1)+(n-2)+... = O(n^2)。

我想请大家看看有没有更高效，更简洁一些的方法呢,请多指教，多谢了
我再补充点哈，我觉得我现在写这个代码感觉不爽，所以我还想看看就算是上面同样的算法，大家有没有一些稍微漂亮点的代码。

1. 
   
2. /*******************/
   
3.   * BinTree structer        *
   
4. /*******************/
   
5. typedef struct BinTree {
   
6.     int key;
   
7.     struct BinTree *pLeft;
   
8.     struct BinTree *pRight;
   
9. }BinTree;
   
10. 
    
11. /* Find the lowest common ancestor of pNode1,pNode2 in bin-tree by the*/
    
12. / *                 name of root,return the pointer to the ancestor .*/
    
13. 
    
14. BinTree * FindLCAncestor(BinTree *root,BinTree *pNode1,BinTree *pNode2)
    
15. {
    
16.         BOOL bFlag1,bFlag2;
    
17.         BinTree *plcAnc,*pTemp;
    
18. 
    
19.         pTemp = root;
    
20.         while(pTemp) {
    
21.                 plcAnc = pTemp;
    
22.                 bFlag1 = bFlag2 = FALSE;
    
23.                                 pTemp = InOrder(root->pLeft,pNode1,pNode2,&bFlag1,&bFlag2);
    
24.                 if(pTemp) {
    
25.                         root = root->pLeft;
    
26.                         continue;
    
27.                 }else {
    
28.                               bFlag1 = bFlag2 = FALSE;
    
29.                                           pTemp = InOrder(root->pRight,pNode1,pNode2,&bFlag1,&bFlag2);
    
30.                 }
    
31.                 if(pTemp) {
    
32.                         root = root->pRight;
    
33.                         continue;
    
34.                 }
    
35.                 else
    
36. 
    
37.                                return plcAnc;
    
38.         }
    
39. }
    
40. 
    
41. /* check whether the two nodes --pNode1 and pNode2 are in the tree root,
    
42. *    if true ,return the pointer to the root, otherwise return NULL. */
    
43. 
    
44. BinTree *InOrder(BinTree *root,
    
45.                    BinTree *pNode1,BinTree *pNode,
    
46.                    BOOL *pFlag1,BOOL *pFlag2)
    
47. {
    
48. 
    
49.         if(!root)
    
50.                 return NULL;
    
51.         if(root->pLeft)
    
52. 
    
53.         InOrder(root->pLeft,pNode1,pNode2,pFlag1,pFlag2);
    
54.         if(root == pNode1)
    
55.                 *pFlag1 = TRUE;
    
56.         if(root == pNode2)
    
57.                 *pFlag2 = TRUE;
    
58.         if(root->pRight)
    
59. 
    
60.         InOrder(root->pRight,pNode1,pNode2,pFlag1,pFlag2);
    
61.         if((*pFlag1) && (*pFlag2))
    
62.                 return root;
    
63.         else
    
64.                 return NULL;
    
65.        
    
66. }
    

复制代码

[ 本帖最后由 lisp 于 2005-11-17 15:43 编辑 ]

win_hate

您看这样行不行:

在结构中加入一个指向 parent 的指针, 然后从 给定的两个节点往 root 走,得到两条路径. 这两条 path 最终是相交的,我们反过来从 root 走这两条路径,看何时分叉即可.

lisp

原帖由 win_hate 于 2005-11-17 15:23 发表
您看这样行不行:

在结构中加入一个指向 parent 的指针, 然后从 给定的两个节点往 root 走,得到两条路径. 这两条 path 最终是相交的,我们反过来从 root 走这两条路径,看何时分叉即可.

这个题是ms的笔试题，题目没有给出指向PARETN的这个指针。当然加入指向parent得指针的话，按您的方法肯定可以搞定。

win_hate

那你遍历这棵树两次,  分别寻找这两个节点, 记下向左走还是向右走的序列, 然后对比.

lisp

原帖由 win_hate 于 2005-11-17 16:13 发表
那你遍历这棵树两次,  分别寻找这两个节点, 记下向左走还是向右走的序列, 然后对比.

多谢多谢，我知道怎么做了，有空把代码写出来。
多谢win_hate多次解惑

win_hate

这样做好象好一些, 遍历一次去搜索其中一个节点, 找到后, 搜索其下是否有另一个节点,如果有,已经解决.如果没有,则在逐层返回时在另一个分支中搜索剩余节点.

在极端的情况下,回退到 root 之后就可以不搜索另一边了.

[ 本帖最后由 win_hate 于 2005-11-17 17:28 编辑 ]

yzc2002

不可行，因为没有父节点的指针

win_hate

是递归实现的,总可以退到上一层

lenovo

分别找到root节点到这两个节点的路径，
最后一个相同的节点就是它们最近的共同祖先。

channel5

如果一个结点a是另外一个结点b的ancestor结点， 那么
返回的是b而不是a。

稍微考虑一下就知道为什么了。