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

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

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

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本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

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

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

《算法导论(原书第2版)》 科曼(Cormen T.H.) (作者), 等 (作者, 译者), 潘金贵 (译者)

《算法导论(原书第2版)》一书深入浅出,全面地介绍了计算机算法。对每一个算法的分析既易于理解又十分有趣,并保持了数学严谨性。本书的设计目标全面,适用于多种用途。涵盖的内容有:算法在计算中的作用,概率分析和随机算法的介绍。本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。本书还介绍了对强连通子图算法正确性的证明,对哈密顿回路和子集求和问题的NP完全性的证明等内容。全书提供了900多个练习题和思考题以及叙述较为详细的实例研究。

更多计算机宝库...