二叉树中的最近公共祖先问题

题目：要求寻找二叉树中两个节点的最近的公共祖先，并将其返回。

view sourceprint?1 class Node   

2 {   

3    Node * left;   

4    Node * right;   

5    Node * parent;   

6 };   

7 /*查找p，q的最近公共祖先并将其返回。*/  

8 Node * NearestCommonAncestor(Node * p,Node * q);

算法思想：这道题的关键在于每个节点中包含指向父节点的指针，这使得程序可以用一个简单的算法实现。首先给出p的父节点p->parent，然后将q的所有父节点依次和p->parent作比较，如果发现两个节点相等，则该节点就是最近公共祖先，直接将其返回。如果没找到相等节点，则将q的所有父节点依次和p->parent->parent作比较......直到p->parent==root。

程序代码：

view sourceprint?01 Node * NearestCommonAncestor(Node * root,Node * p,Node * q)   

02 {   

03     Node * temp;   

04          while(p!=NULL)   

05     {   

06         p=p->parent;   

07         temp=q;   

08         while(temp!=NULL)   

09         {   

10             if(p==temp->parent)   

11                 return p;   

12             temp=temp->parent;   

13         }   

14     }   

15 }

题目：将一个单链表逆转——原来的头指针变为尾指针，原来的尾指针变为头指针。

算法思想：从链表的头结点开始依次逆转，最终将整个链表逆转。

程序代码：

view sourceprint?01 /*节点的类定义*/  

02 class Node   

03 {   

04     Node * next;   

05 };   

06     

07 /*链表的类定义*/  

08 class List   

09 {   

10     Node * head;   

11 };   

12     

13 /*逆转函数——将一个单链表逆转*/  

14 void ReverseList(List & list)   

15 {   

16     Node * pre=NULL;   

17     Node * cur=list.head;   

18     Node * back=cur->next;   

19     

20     while(back!=NULL)   

21     {   

22         cur->next=pre;   

23         pre=cur;   

24         cur=back;   

25         back=cur->next;   

26     }   

27     

28 }

知识拓展：对于第二个二叉树的问题，如果节点中不包含指向父节点的指针应该怎么计算？

算法思想：如果一个节点的左子树包含p，q中的一个节点，右子树包含另一个，则这个节点就是p，q的最近公共祖先。

程序代码：

view sourceprint?01 /*查找a，b的最近公共祖先，root为根节点，out为最近公共祖先的指针地址*/  

02 int FindNCA(Node* root, Node* a, Node* b, Node** out)    

03 {    

04     if( root == null )    

05     {    

06         return 0;    

07     }   

08     

09     if( root == a || root == b )   

10     {       

11         return 1;   

12     }   

13     

14     int iLeft = FindNCA(root->left, a, b, out);   

15     if( iLeft == 2 )   

16     {       

17         return 2;   

18     }   

19     

20     int iRight = FindNCA(root->right, a, b, out);   

21     if( iRight == 2 )   

22     {       

23         return 2;   

24     }   

25     

26     if( iLeft + iRight == 2 )   

27     {      

28         *out == root;   

29     }   

30     return iLeft + iRight;   

31 }   

32     

33 void main()    

34 {    

35     Node* root = ...;    

36     Node* a = ...;    

37     Node* b = ...;    

38     Node* out = null;    

39     int i = FindNCA(root, a, b, &out);    

40     if( i == 2 )    

41     {    

42         printf("Result pointer is %p", out);    

43     }    

44     else   

45     {    

46         printf("Not find pointer");    

47     }    

48 }