对于一颗给定的二叉树，对任意两个节点，求它们的最低的公共祖先。
下面就是这样一道题，给定一棵树的前序和中序遍历（我们知道这颗树就是确定的了），对于任两个节点，求它们的最低公共主祖先。
PAT题目：1151 LCA in a Binary Tree （30 分）
#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
int* pre,*in;
map<int,int> pos;
void LCA(int preRoot,int inL,int inR,int u,int v){
if(inL>inR) return;
//inRoot,u,v:根节点,u,v在中序遍历的位置
int inRoot=pos[pre[preRoot]],uInIdx=pos[u],vInIdx=pos[v];
if(uInIdx<inRoot&&vInIdx<inRoot){//u,v在中序遍历中的位置小于根
LCA(preRoot+1,inL,inRoot-1,u,v);
}else if((uInIdx<inRoot&&vInIdx>inRoot)
||(uInIdx>inRoot&&vInIdx<inRoot)){
printf("LCA of %d and %d is %d.\n",u,v,in[inRoot]);
}else if(uInIdx>inRoot&&vInIdx>inRoot){
LCA(preRoot+1+(inRoot-inL),inRoot+1,inR,u,v);
}else{
if(uInIdx==inRoot){
printf("%d is an ancestor of %d.\n",u,v);
}else if(vInIdx==inRoot){
printf("%d is an ancestor of %d.\n",v,u);
}
}
}
int main(){
int m,n;
scanf("%d%d",&m,&n);
in=new int[n+1];
pre=new int[n+1];
for(int i=1;i<=n;i++){
scanf("%d",&in[i]);
pos[in[i]]=i;
}
for(int i=1;i<=n;i++){
scanf("%d",&pre[i]);
}
while(m--){
int a,b;
scanf("%d%d",&a,&b);
if(pos[a]==0&&pos[b]==0){
printf("ERROR: %d and %d are not found.\n",a,b);
}else if(pos[a]==0){
printf("ERROR: %d is not found.\n",a);
}else if(pos[b]==0){
printf("ERROR: %d is not found.\n",b);
}else{
LCA(1,1,n,a,b);
}
}
return 0;
}上面是对于一颗普通的二叉树，如果这颗二叉树又是一个二叉搜索树，那么还有如下的方法可用，而且是更好的方式，用上面的方法就会超时。
题目：1143 Lowest Common Ancestor （30 分）
#include <iostream>
#include <algorithm>
#include <unordered_set>
#define MAXSIZE 10001
using namespace std;
struct Node{
int val;
Node *lchild, *rchild;
Node(int v){
val = v;
lchild = rchild = NULL;
}
};
int pre[MAXSIZE] = {0}, in[MAXSIZE] = {0};
Node * inPreCreateTree(int inL, int inR, int preL, int preR){
if( preL > preR ){
return NULL;
}
int val = pre[preL];
Node * root = new Node(val);
int mid;
for( mid = inL; mid <= inR; mid++ ){
if( in[mid] == val ){
break;
}
}
int numLeft = mid - inL;
root->lchild = inPreCreateTree(inL, mid-1, preL+1, preL+numLeft);
root->rchild = inPreCreateTree(mid+1, inR, preL+numLeft+1, preR);
return root;
}
void LCA(Node * root, int lVal, int rVal, bool positionChanged){
if( root != NULL ){
if( root->val > lVal && root->val < rVal ){
if( positionChanged == false ){
cout<<"LCA of "<<lVal<<" and "<<rVal<<" is "<<root->val<<".\n";
}else{
cout<<"LCA of "<<rVal<<" and "<<lVal<<" is "<<root->val<<".\n";
}
}else if( root->val == lVal ){
cout<<lVal<<" is an ancestor of "<<rVal<<".\n";
}else if( root->val == rVal ){
cout<<rVal<<" is an ancestor of "<<lVal<<".\n";
}else if( root->val > rVal ){
LCA(root->lchild, lVal, rVal, positionChanged);
}else{
LCA(root->rchild, lVal, rVal, positionChanged);
}
}
}
int main(){
// ios::sync_with_stdio(false);
// cin.tie(0);
int m, n;
cin>>m>>n;
int val;
unordered_set<int> s;
for( int i = 0; i < n; i++ ){
cin>>val;
in[i] = pre[i] = val;
s.insert(val);
}
sort(in, in+n);
Node * root = inPreCreateTree(0, n-1, 0, n-1);
int u, v;
for( int i = 0; i < m; i++ ){
cin>>u>>v;
if( s.find(u) == s.end() && s.find(v) == s.end() ){
cout<<"ERROR: "<<u<<" and "<<v<<" are not found.\n";
}else if( s.find(u) == s.end() ){
cout<<"ERROR: "<<u<<" is not found.\n";
}else if( s.find(v) == s.end() ){
cout<<"ERROR: "<<v<<" is not found.\n";
}else{
bool positionChanged = false;
if( u >= v ){
swap(u, v);
positionChanged = true;
}
LCA(root, u, v, positionChanged);
}
}
return 0;
}方法2：
该方法对于这题会有一个测试点超时
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
const int maxn=10010;
int pre[maxn],in[maxn];
map<int,int> pos;
void LCA(int preRoot,int inL,int inR,int u,int v){
if(inL>inR) return;
int uInIdx=pos[u],vInIdx=pos[v];
int inRoot=pos[pre[preRoot]];
if(uInIdx<inRoot&&vInIdx<inRoot){
LCA(preRoot+1,inL,inRoot-1,u,v);
}else if(uInIdx<inRoot&&vInIdx>inRoot||(uInIdx>inRoot&&vInIdx<inRoot)){
printf("LCA of %d and %d is %d.\n",u,v,pre[preRoot]);
}else if(uInIdx>inRoot&&vInIdx>inRoot){
LCA(preRoot+(inRoot-inL)+1,inRoot+1,inR,u,v);
}else{
if(uInIdx=inRoot){
printf("%d is an ancestor of %d.\n",u,v);
}else if(vInIdx==inRoot){
printf("%d is an ancestor of %d.\n",v,u);
}
}
}
int main(){
int m,n;
cin>>m>>n;
for(int i=1;i<=n;i++){
cin>>pre[i];
in[i]=pre[i];
}
sort(in+1,in+n+1);
for(int i=1;i<=n;i++){
pos[in[i]]=i;
}
while(m--){
int a,b;
cin>>a>>b;
if(pos[a]==0&&pos[b]==0){
printf("ERROR: %d and %d are not found.\n",a,b);
}else if(pos[a]==0){
printf("ERROR: %d is not found.\n",a);
}else if(pos[b]==0){
printf("ERROR: %d is not found.\n",b);
}else{
LCA(1,1,n,a,b);
}
}
return 0;
}
转播
