查找二叉树的公共父节点.doc

寻找二叉树中两个节点的最近的公共祖先迅雷笔试归来分类：C/C+学习笔记2010-10-28 10:38779人阅读评论(4)收藏举报迅雷的笔试可真让人煎熬啊，题量很大，而且考试时间是三个小时。不过迅雷的题目质量很高，既考查了基础知识又不乏高难的数据结构和算法题目。下面和大家分享两道算法编程题，代码没有在编译器上调试，可能会出现一点小bug，感兴趣的朋友可以编译调试一下。题目1：将一个单链表逆转原来的头指针变为尾指针，原来的尾指针变为头指针。算法思想：从链表的头结点开始依次逆转，最终将整个链表逆转。程序代码：view plain1. /*节点的类定义*/2. classNode3. 4. Node*next;5. ;6. 7. /*链表的类定义*/8. classList9. 10. Node*head;11. ;12. 13. /*逆转函数将一个单链表逆转*/14. voidReverseList(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. 题目2：要求寻找二叉树中两个节点的最近的公共祖先，并将其返回。view plain1. classNode2. 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 plain1. Node*NearestCommonAncestor(Node*root,Node*p,Node*q)2. 3. Node*temp;4. while(p!=NULL)5. 6. p=p-parent;7. temp=q;8. while(temp!=NULL)9. 10. if(p=temp-parent)11. returnp;12. temp=temp-parent;13. 14. 15. 知识拓展：对于第二个二叉树的问题，如果节点中不包含指向父节点的指针应该怎么计算？算法思想：如果一个节点的左子树包含p，q中的一个节点，右子树包含另一个，则这个节点就是p，q的最近公共祖先。程序代码：view plain1. /*查找a，b的最近公共祖先，root为根节点，out为最近公共祖先的指针地址*/2. intFindNCA(Node*root,Node*a,Node*b,Node*out)3. 4. if(root=null)5. 6. return0;7. 8. 9. if(root=a|root=b)10. 11. return1;12. 13. 14. intiLeft=FindNCA(root-left,a,b,out);15. if(iLeft=2)16. 17. return2;18. 19. 20. intiRight=FindNCA(root-right,a,b,out);21. if(iRight=2)22. 23. return2;24. 25. 26. if(iLeft+iRight=2)27. 28. *out=root;29. 30. returniLeft+iRight;31. 32. 33. voidmain()34. 35. Node*root=.;36. Node*a=.;37. Node*b=.;38. Node*out=null;39. inti=FindNCA(root,a,b,&out);40. if