PAT 甲级 1151 LCA in a Binary Tree（30 分）

原题地址：PAT Adv 1151

题目正文：

1151 LCA in a Binary Tree（30 分）

The lowest common ancestor (LCA) of two nodes U and V in a tree is the deepest node that has both U and V as descendants.

Given any two nodes in a binary tree, you are supposed to find their LCA.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers: M (≤ 1,000), the number of pairs of nodes to be tested; and N (≤ 10,000), the number of keys in the binary tree, respectively. In each of the following two lines, N distinct integers are given as the inorder and preorder traversal sequences of the binary tree, respectively. It is guaranteed that the binary tree can be uniquely determined by the input sequences. Then M lines follow, each contains a pair of integer keys U and V. All the keys are in the range of int.

Output Specification:

For each given pair of U and V, print in a line LCA of U and V is A. if the LCA is found and A is the key. But if A is one of U and V, print X is an ancestor of Y. where X is A and Y is the other node. If U or V is not found in the binary tree, print in a line ERROR: U is not found. or ERROR: V is not found. or ERROR: U and V are not found..

Sample Input:

6 8
7 2 3 4 6 5 1 8
5 3 7 2 6 4 8 1
2 6
8 1
7 9
12 -3
0 8
99 99

Sample Output:

LCA of 2 and 6 is 3.
8 is an ancestor of 1.
ERROR: 9 is not found.
ERROR: 12 and -3 are not found.
ERROR: 0 is not found.
ERROR: 99 and 99 are not found.

 题目说明：

为了查找两个节点的最低公共祖先，即是查找同时包含这两个节点的最小子树的根节点。这个根节点满足在中序序列中出现在需要查找LCA的两个节点的中间。例如，要查找中序中的第i个和第j个的LCA，显然，为了使答案存在i≠j，不妨设i<j，那么要查找的中序中第a个出现的元素，其中i、j、a满足i≤a≤j，然而，这个不等式只是满足LCA的必要条件，非充分，而这个不等式的成立是由中序遍历的特点决定的，这一点不懂的请自行去画图看看。

为了满足充分性，我们还应该在满足上述条件的前提下，在那些满足处于第i个和第j个之间（包含）的元素中寻找在先序遍历中出现的第一个元素。换句话说在先序遍历中寻找第一个出现的满足i≤a≤j的中序遍历的第a个元素。为了方便理解，请看如下的一种情况

图中红色的节点均会在中序遍历中出现在i及j的顺序之间，但是只有第a个才会在先序中第一个出现，这个是由最底层公共祖先这个设定决定的。

接下来，就是将中序顺序的值和中序的顺序对应起来，因为树中的值是各不相同的，所以这个映射也是唯一的，别忘了记录反函数。那么在读取先序序列的时候就可将先序序列按其值的中序顺序的排列顺序值来映射一遍。姑且称其为被编码的先序序列。

啰嗦一点，目的是在被编码的先序序列中查找到第一个出现的满足i≤a≤j的a值，其中，i和j分别代表待查最底层公共祖先元素对对应的中序顺序值，而a则是满足出现在顺序值i和j之间的顺序值，当a满足在被编码的先序序列中从头遍历第一个出现的时候，这个a顺序对应的就是最底层公共祖先。

想象一种更容易理解的过程，在使用中序序列将值编码为顺序出现的次序时，这个过程其实就是在搭建一个二叉搜索树。接下来在被编码的先序序列中查找满足条件的值的过程，可以对应上二叉搜索树上的寻找到两个节点的分支点（即最小公共子树的根）的过程。

如何加速这个查找过程呢？

无论树状数组、线段树还是分块法仅适合存储区间极大值、极小值或区间和等单值信息，无法保证区间内一定存在处于极大值和极小值之间的某元素。但是，如果该区间内存在一个满足条件的值，那么区间内的极大值不可能小于min(i,j)，同理区间内的极小值不能大于max(i,j)，这是该区间内存在一个满足条件（i≤a≤j）的值的必要条件，虽非充分，但是确实在一定程度上加速了寻找的过程，我们能够通过两次比较舍去一段肯定不合适的区间。但是，若（i≤区间极小值≤j）或（i≤区间极大值≤j），那么区间内一定存在至少一个满足条件的值，即为极小值或极大值。而（区间极小值≤i && j≤区间极大值）的情况下必须遍历整个区间才能确定是否存在满足条件的值。在这里，分块法的加速效果和实际的数据有序程度密切相关。

综上所述，我拟采用如下思路求解：

1、使用哈希桶实现接近常数的快速编解码，通过调用unordered_map实现。

2、使用中序顺序值的先序来寻找LCA，即根据节点值的唯一性搭建二叉搜索树。

3、使用分块法在一定程度上加速寻找满足范围的第一个值。

4、使用输入挂加速读取操作。

实现代码：

#include<bits/stdc++.h>
using namespace std;
struct node{                //block maximum & minimum
    int Min=INT_MAX,Max=INT_MIN;
};
int read(){                 //fast read-in
    int input=0, flag=1;
    char c=getchar();
    while((c<'0' || c>'9') && c!='-')
        c=getchar();
    if(c=='-'){             //if below zero
        flag=0;
        c=getchar();
    }
    while(c>='0' && c<='9'){
        input=input*10 + c - '0';
        c=getchar();
    }
    return flag? input : ~input+1;
}
int main(){
    int n,m,tmp, blockid, x, y, a;
    cin >> m >> n;
    unordered_map<int,int> encrypt,decrypt;
    for(int i=1;i<=n;i++){
        tmp=read();
        encrypt[tmp]=i;         //encrypt procedure
        decrypt[i]=tmp;         //decrypt procedure
    }
    int blocksize = ceil( sqrt(n) );
    int blockcnt = n%blocksize? n/blocksize+1 : n/blocksize;
    vector<node> block(blockcnt);
    vector<int> pre(n);
    for(int i=0;i<n;i++){
        tmp=encrypt[read()];
        pre[i]=tmp;                                         //encrypt the pre-sequence
        blockid=i/blocksize;
        block[blockid].Max=max(block[blockid].Max,tmp);     //construction of block matrix
        block[blockid].Min=min(block[blockid].Min,tmp);
    }
    while(m--){
        x=read(), y=read();
        if(!encrypt[x] && !encrypt[y])                      //if both not in the tree
            printf("ERROR: %d and %d are not found.\n",x,y);
        else if(!encrypt[x] || !encrypt[y])                 //if one node is not in the tree
            printf("ERROR: %d is not found.\n",!encrypt[x]?x:y);
        else{
            x=encrypt[x], y=encrypt[y];                     //acquire the encrypted value of the two node
            int larger=max(x,y), smaller=min(x,y);
            bool found=false;
            for(blockid=0; !found ;blockid++){              //if not found, traverse all blocks
                if(block[blockid].Max<smaller || block[blockid].Min>larger)
                    continue;
                for(int i=blockid*blocksize;i<(blockid+1)*blocksize;++i){   //for a potential block, traverse all elements within the block
                    if(smaller<=pre[i] && pre[i]<=larger){
                        a=pre[i];
                        found=true;
                        break;
                    }
                }
            }
            if(a==x || a==y)
                printf("%d is an ancestor of %d.\n",a==x?decrypt[x]:decrypt[y],a==x?decrypt[y]:decrypt[x]); //decrypt & output result
            else
                printf("LCA of %d and %d is %d.\n",decrypt[x],decrypt[y],decrypt[a]);
        }
    }
    return 0;
}

运行时间截图：

 

实现了较高的效率。