【1151】LCA in a Binary Tree (30分)【倍增法解决LCA】

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>  
#include<map>
#include<vector>
#include<queue> 
using namespace std;
struct Node{//结点类
  int data,father,level;//点权值，父结点在pre中的下标，深度
  Node(int d=0,int f=-1,int l=0):data(d),father(f),level(l){}
};
const int MAX=10005;
Node pre[MAX];//pre[i]为当前结点i的父节点
int n,m,in[MAX];
//确定每个结点的父节点和深度
void createTree(int root,int left,int right,int father,int level){
  if(left>right)
    return;
  int i=left;
  while(i<=right && in[i]!=pre[root].data)
    ++i;//找到根结点在中序遍历序列中的位置i
  pre[root]=Node(pre[root].data,father,level);
  //确定当前子树根结点的父结点和深度
  createTree(root+1,    left,i-1,   root,    level+1);//递归处理左子树
  createTree(root+1+i-left,   i+1,right,   root,    level+1);
}
int main(){   
  int m,n,a,b;
  scanf("%d %d",&m,&n);//测试m对结点,树共n个结点
  for(int i=0;i<n;i++){
    scanf("%d",&in[i]);//存储中序序列
  }
  for(int i=0;i<n;i++)
    scanf("%d",&pre[i].data);
  createTree(0,0,n-1,-1,0);
  for(int i=0;i<m;i++){
    int a,b;
    scanf("%d%d",&a,&b);//找a和b两个结点的LCA
    int ia=n,ib=n;
    for(int i=0;i<n;i++){//找到两个结点在pre数组的下标
      if(pre[i].data==a)
        ia=i;
      if(pre[i].data==b)
        ib=i;
    }
    if(ia==n&&ib==n){
      printf("ERROR: %d and %d are not found.\n",a,b);
    }else if(ia==n){
      printf("ERROR: %d is not found.\n",a);
    }else if(ib==n){
      printf("ERROR: %d is not found.\n",b);
    }else{
      bool f=true;//true表示a的深度更大
      if(pre[ia].level <pre[ib].level){//让ia指向深度更大的结点
        swap(ia,ib);
        f=false;
      }
      while(pre[ia].level>pre[ib].level)//将二者调整到同一深度
        ia=pre[ia].father;
      if(ia==ib){
        printf("%d is an ancestor of %d.\n",pre[ia].data,f?a:b);
      }else{
        while(ia!=ib){//ia，ib同时向上调整，直至二者指向同一结点
          ia=pre[ia].father;
          ib=pre[ib].father;
        }
        printf("LCA of %d and %d is %d.\n",a,b,pre[ia].data);
      }
    }
  }
  system("pause");
    return 0;   
}