首页 > 代码库 > careercup-树与图 4.7
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[10]= {29,4,6,1,8,3,0,78,23,89}; 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, 0); BinarySearchTree*n2 = search(root, 4); 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 0;}
careercup-树与图 4.7
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。