careercup-树与图 4.7

4.7 设计并实现一个算法，找出二叉树中某两个结点的第一个共同祖先。不得将额外的结点储存在另外的数据结构中。注意：这不一定是二叉查找树。

解答

本题的关键应当是在Avoid storing additional nodes in a data structure 这句话上。我的理解是，不允许开额外的空间(比如说一个数组)来存储作为中间变量的结点。虽然我也怀疑它是不是说不允许在结点数据结构Node中加入额外的东西，比如说父结点的指针。Anyway，我们先从最简单的入手，再一步步加入限制条件。

如果没有任何限制条件，那我觉得最直观的思路就是把其中一个点的所有祖先(包含它自身) 都放入一个哈希表，然后再一步步查找另一个点的祖先结点，第一个在哈希表中出现的祖先结点即为题目所求。

代码如下，用map模拟(当然，效率比不上哈希表)：

算法：

//要使用额外的空间

BinarySearchTree* findFirstAncestor(BinarySearchTree *x,BinarySearchTree *y)

{

    if(x==NULL||y==NULL)

        return NULL;

    map<BinarySearchTree*,bool> mp;

    while(x)

    {

        mp[x]=true;

        x=x->parent;

    }

    while(y)

    {

        if(mp[y])

            return y;

        y=y->parent;

    }

    return y;

}

这里用了一个map来存储中间变量，如果题目不允许开额外的辅助空间，那该如何做呢？那就老老实实地一个个地试。不断地取出其中一个结点的父结点，然后判断这个结点是否也为另一个结点的父结点。代码如下：

bool father(BinarySearchTree *x,BinarySearchTree *y)

{

    if(x==NULL||y==NULL)

        return false;

    if(x==y)

        return true;

    return father(x->left,y)||father(x->right,y);

}

//将每一x的祖先拿出来判断是否为y的祖先，从下到上的方法

BinarySearchTree* find_first_ancestor(BinarySearchTree *x,BinarySearchTree *y)

{

    while(x)

    {

        if(father(x,y))

            return x;

        x=x->parent;

    }

    return x;

}

让我们把条件再限制地严苛一些，如果数据结构Node中不允许有指向父亲结点的指针，那么我们又该如何处理？其实也很简单，首先根结点一定为任意两个结点的共同祖先，从根结点不断往下找，直到找到最后一个这两结点的共同祖先，即为题目所求。代码如下：

BinarySearchTree* find_ancestor(BinarySearchTree *root,BinarySearchTree *x,BinarySearchTree *y,BinarySearchTree *&ret)

{

    if(x==NULL||y==NULL)

        return NULL;

    if(root&&father(root,x)&&father(root,y))

    {

        ret=root;

        find_ancestor(root->left,x,y,ret);

        find_ancestor(root->right,x,y,ret);

    }

    return ret;

}

这里用到了递归，ans最终保存的是这两个结点从根结点算起最后找到的那个祖先。因为从根结点开始，每次找到满足要求的结点，ans都会被更新。

C++完整代码：

#include<iostream>

#include<new>

#include<map>

using namespace std;

struct BinarySearchTree

{

    int elem;

    BinarySearchTree *parent;

    BinarySearchTree *left;

    BinarySearchTree *right;

    BinarySearchTree(int x):elem(x),parent(NULL),left(NULL),right(NULL) {}

};

void insert(BinarySearchTree *&root,int z)

{

    BinarySearchTree *y=new BinarySearchTree(z);

    if(root==NULL)

    {

        root=y;

        return;

    }

    else if(root->left==NULL&&z<root->elem)

    {

        root->left=y;

        y->parent=root;

        return;

    }

    else if(root->right==NULL&&z>root->elem)

    {

        root->right=y;

        y->parent=root;

        return;

    }

    if(z<root->elem)

        insert(root->left,z);

    else

        insert(root->right,z);

}

void createBST(BinarySearchTree *&root)

{

    int arr[]= {,,,,,,,,,};

    for(auto a:arr)

        insert(root,a);

}

void inorder(BinarySearchTree *root)

{

    if(root)

    {

        inorder(root->left);

        cout<<root->elem<<" ";

        inorder(root->right);

    }

}

BinarySearchTree* findMin(BinarySearchTree *root)

{

    if(root==NULL||!root->left)

        return root;

    while(root->left)

    {

        root=root->left;

    }

    return root;

}

BinarySearchTree* findMax(BinarySearchTree *root)

{

    if(root==NULL||!root->right)

        return root;

    while(root->right)

    {

        root=root->right;

    }

    return root;

}

BinarySearchTree* findProcessor(BinarySearchTree* x)

{

    if(x->left)

        return findMax(x->left);

    BinarySearchTree *y=x->parent;

    while(y&&y->left==x)

    {

        x=y;

        y=x->parent;

    }

    return y;

}

BinarySearchTree* findSuccessor(BinarySearchTree *x)

{

    if(x->right)

        return findMin(x->right);

    BinarySearchTree *y=x->parent;

    while(y&&y->right==x)

    {

        x=y;

        y=x->parent;

    }

    return y;

}

//要使用额外的空间

BinarySearchTree* findFirstAncestor(BinarySearchTree *x,BinarySearchTree *y)

{

    if(x==NULL||y==NULL)

        return NULL;

    map<BinarySearchTree*,bool> mp;

    while(x)

    {

        mp[x]=true;

        x=x->parent;

    }

    while(y)

    {

        if(mp[y])

            return y;

        y=y->parent;

    }

    return y;

}

bool father(BinarySearchTree *x,BinarySearchTree *y)

{

    if(x==NULL||y==NULL)

        return false;

    if(x==y)

        return true;

    return father(x->left,y)||father(x->right,y);

}

//将每一x的祖先拿出来判断是否为y的祖先，从下到上的方法

BinarySearchTree* find_first_ancestor(BinarySearchTree *x,BinarySearchTree *y)

{

    while(x)

    {

        if(father(x,y))

            return x;

        x=x->parent;

    }

    return x;

}

//从上到下的方法

BinarySearchTree* find_ancestor(BinarySearchTree *root,BinarySearchTree *x,BinarySearchTree *y,BinarySearchTree *&ret)

{

    if(x==NULL||y==NULL)

        return NULL;

    if(root&&father(root,x)&&father(root,y))

    {

        ret=root;

        find_ancestor(root->left,x,y,ret);

        find_ancestor(root->right,x,y,ret);

    }

    return ret;

}

BinarySearchTree* search(BinarySearchTree* head, int x)

{

    if(head == NULL) return NULL;

    if(x == head->elem)

        return head;

    else if(x <= head->elem)

        return search(head->left, x);

    else

        return search(head->right, x);

}

int main()

{

    BinarySearchTree *root=NULL;

    createBST(root);

    inorder(root);

    cout<<endl;

    BinarySearchTree *n1 = search(root, );

    BinarySearchTree*n2 = search(root, );

    cout<<n1->elem<<" "<<n2->elem<<endl;

    BinarySearchTree *ans = find_first_ancestor(n1, n2);

    cout<<ans->elem<<endl;

    BinarySearchTree *ans1 = NULL;

    find_ancestor(root, n1, n2, ans1);

    cout<<ans1->elem<<endl;

    BinarySearchTree *pre=findProcessor(n2);

    cout<<pre->elem<<endl;

    BinarySearchTree *post=findSuccessor(n2);

    cout<<post->elem<<endl;

    return ;

}

巴特西

careercup-树与图 4.7

解答

最新文章

热门文章