寻找二叉树两个节点的最近公共祖先

最近公共祖先问题
服务器君一共花费了410.984 ms进行了5次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

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

class Node  
{  
   Node * left;  
   Node * right;  
   Node * parent;  
};  
/*查找p,q的最近公共祖先并将其返回。*/  
Node * NearestCommonAncestor(Node * p,Node * q);  

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

程序代码:

Node * NearestCommonAncestor(Node * root,Node * p,Node * q)  
{  
    Node * temp;  
         while(p!=NULL)  
    {  
        p=p->parent;  
        temp=q;  
        while(temp!=NULL)  
        {  
            if(p==temp->parent)  
                return p;  
            temp=temp->parent;  
        }  
    }  
}  

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

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

程序代码:

/*节点的类定义*/  
class Node  
{  
    Node * next;  
};  
  
/*链表的类定义*/  
class List  
{  
    Node * head;  
};  
  
/*逆转函数——将一个单链表逆转*/  
void ReverseList(List & list)  
{  
    Node * pre=NULL;  
    Node * cur=list.head;  
    Node * back=cur->next;  
  
    while(back!=NULL)  
    {  
        cur->next=pre;  
        pre=cur;  
        cur=back;  
        back=cur->next;  
    }  
  
}  

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

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

程序代码:

/*查找a,b的最近公共祖先,root为根节点,out为最近公共祖先的指针地址*/  
int FindNCA(Node* root, Node* a, Node* b, Node** out)   
{   
    if( root == null )   
    {   
        return 0;   
    }  
  
    if( root == a || root == b )  
    {      
        return 1;  
    }  
  
    int iLeft = FindNCA(root->left, a, b, out);  
    if( iLeft == 2 )  
    {      
        return 2;  
    }  
  
    int iRight = FindNCA(root->right, a, b, out);  
    if( iRight == 2 )  
    {      
        return 2;  
    }  
  
    if( iLeft + iRight == 2 )  
    {     
        *out == root;  
    }  
    return iLeft + iRight;  
}  
  
void main()   
{   
    Node* root = ...;   
    Node* a = ...;   
    Node* b = ...;   
    Node* out = null;   
    int i = FindNCA(root, a, b, &out);   
    if( i == 2 )   
    {   
        printf("Result pointer is %p", out);   
    }   
    else   
    {   
        printf("Not find pointer");   
    }   
}  

本文地址:http://www.nowamagic.net/librarys/veda/detail/974,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/974

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《C专家编程》 林登 (LinDen.P.V.D) (作者), 徐波 (译者)

《C专家编程》展示了最优秀的C程序员所使用的编码技巧,并专门开辟了一章对C++的基础知识进行了介绍。书中C的历史、语言特性、声明、数组、指针、链接、运行时、内存以及如何进一步学习C++等问题进行了细致的讲解和深入的分析。全书撷取几十个实例进行讲解,对C程序员具有非常高的实用价值。《C专家编程》可以帮助有一定经验的C程序员成为C编程方面的专家,对于具备相当的C语言基础的程序员,《C专家编程》可以帮助他们站在C的高度了解和学习C++。

更多计算机宝库...