PAT 1151 LCA in a Binary Tree

这一题的大意是给出一个BST的前序遍历，让我们在这棵BST二叉树中，给出两个的点，判断这两个点在这棵二叉树的最近公共祖先是谁，这两个点可能并不在树中，也有可能给出的节点是另一个节点的祖先，我们需要针对不同情况，做出不同的判断。
因为题目给出的节点的值是在int范围内，也就是说这个值可能会很大，我们可以选择离散化，把N个值映射到1-N，这样我们就可以用int depp[10005]直接来表示某一个节点的深度了。与unordered_map<int,int>来说速度更快了，因为是BST，所以中序遍历的节点就是将所有值从小到大排序的结果。实际上不用离散化也可以吧，
可以参考这一题：

PAT 1151 LCA in a Binary Tree

但BST中序遍历是升序的，用离散化也可以在建树的过程中少写一个for循环查找中序遍历中根节点的位置。
我们可以根据中序遍历和前序遍历来建树，用哈希表来存储节点，从而可以来找任意两个节点的公共祖先。
因为只需要找公共祖先，所以我们不用存储孩子节点，只需要找到每一个节点的父亲节点，和它的深度即可。
根据前序遍历和中序遍历的建树方法已经写过多次了，这里不再赘述，在建好树后，我们就需要关注如何找两个节点的最近公共祖先。
我们只需要保证当深度相同时，两个节点都去看它的父亲节点，如果一个节点的深度比另一个节点大，那么我们先去看这个深度深的节点，同时看深度深的节点的祖先节点是否会等于另一个节点。 直到两个节点深度一样。
大致思路就是如上
完整代码如下：

#include<bits/stdc++.h>#include<iostream>usingnamespacestd;intM;intN;unordered_map<int,int>parent;vector<int>preorder;vector<int>inorder;vector<int>temp;unordered_map<int,int>last;intdeep[10005];unordered_map<int,int>mp;intbuild(intprestart,intpreend,intinstart,intinend,intd){if(prestart>preend||instart>inend){return-1;}introot=preorder[prestart];deep[root]=d;intindex=root-1;intlen=index-instart;intxl=build(prestart+1,prestart+len,instart,instart+len-1,d+1);if(xl!=-1)parent[xl]=root;intxr=build(prestart+len+1,preend,instart+len+1,inend,d+1);if(xr!=-1)parent[xr]=root;returnroot;}intmain(){cin>>M>>N;for(inti=0;i<N;i++){intx;cin>>x;preorder.push_back(x);}temp=preorder;sort(temp.begin(),temp.end());for(inti=0;i<temp.size();i++){mp[temp[i]]=i+1;last[i+1]=temp[i];temp[i]=i+1;}inorder=temp;for(inti=0;i<preorder.size();i++){preorder[i]=mp[preorder[i]];}introot=build(0,N-1,0,N-1,0);intu;intv;for(inti=0;i<M;i++){cin>>u>>v;if(!mp.count(u)&&!mp.count(v)){//如果u和v都不存在printf("ERROR: %d and %d are not found.\n",u,v);continue;}elseif(!mp.count(u)){printf("ERROR: %d is not found.\n",u);continue;}elseif(!mp.count(v)){printf("ERROR: %d is not found.\n",v);continue;}//现在要找最近公共祖先了//先把u，v离散//如果它们不再同一层，那么就需要把它们放到同一层inttempu=mp[u];inttempv=mp[v];if(tempu==tempv){printf("%d is an ancestor of %d.\n",u,v);continue;}boolflag=0;while(tempu!=root||tempv!=root){if(deep[tempu]>deep[tempv]){if(parent[tempu]==tempv){//说明v是u的ancestorflag=1;printf("%d is an ancestor of %d.\n",v,u);break;}tempu=parent[tempu];}elseif(deep[tempu]==deep[tempv]){if(parent[tempu]==parent[tempv]){flag=1;printf("LCA of %d and %d is %d.\n",u,v,last[parent[tempu]]);break;}tempu=parent[tempu];tempv=parent[tempv];}else{if(parent[tempv]==tempu){//说明u是v的ancestorflag=1;printf("%d is an ancestor of %d.\n",u,v);break;}tempv=parent[tempv];}}if(flag==0){printf("LCA of %d and %d is %d.\n",u,v,last[parent[tempu]]);}}return0;}

注意，给出的两个节点可能是同一个，我们要进行特判。

inttempu=mp[u];inttempv=mp[v];if(tempu==tempv){printf("%d is an ancestor of %d.\n",u,v);continue;}

总结：这一题就是BST建树+最近公共祖先的求法，我们用根据实际情况灵活建树。