PAT甲级1151 LCA in a Binary Tree (30 分)：[C++题解]LCA、最低公共祖先、哈希表映射

本文主要是介绍PAT甲级1151 LCA in a Binary Tree (30 分)：[C++题解]LCA、最低公共祖先、哈希表映射，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- 题目分析
- 题目链接

题目分析

在这里插入图片描述

来源：acwing
分析：

和下面这道题几乎是同一题：PAT甲级1143 Lowest Common Ancestor (30 分)：[C++题解]LCA、最低公共祖先
这道题先是根据给定的中序遍历和先序遍历，建树。
建树的时候需要用到点的深度和每个点的父节点是什么。

然后是找LCA,有很多优秀的算法，这里使用朴素做法，O(n)复杂度。思想是：两个结点a和b，深度深的往上等于它的父节点；如果两者位于同一层，任意一个往上走等于它的父亲，直到两者相等。相等时就是最低公共祖先。

while( a != b){if(depth[a] < depth[b]) b =p[b];else a = p[a];
}

本题需要注意的使用哈希表pos映射进行离散化到0~n-1，seq数组记录映射之前的数。因为题目给的数据是int范围内的，不离散化查找容易超时。离散化代码：

//读入中序for(int i = 0; i< n; i++) {cin >> seq[i]; //读入中序pos[seq[i]] =i; //保存中序序列映射后的值in[i] =i; //中序遍历映射到0~n-1}//读入前序for(int i = 0; i<n; i++) {cin >> pre[i];pre[i] = pos[pre[i]]; //前序遍历进行映射}

ac代码

#include<bits/stdc++.h>
using namespace std;
const int N = 10010;int in[N],pre[N],seq[N];
int n, m;
unordered_map<int,int> pos;
int p[N],depth[N];//根据中序遍历和前序遍历建树
int  build( int il ,int ir ,int pl ,int pr ,int  d){int root = pre[pl];int k = root;depth [root] = d;if(il < k) p[build(il , k -1 , pl+1, pl+1 + k -1 -il , d+1)]  = root;if( k< ir) p[build(k+1,ir ,pl+ k - il+1, pr,d+1)] =root ;return root;
}int main(){cin >> m >> n;//读入中序for(int i = 0; i< n; i++) {cin >> seq[i];pos[seq[i]] =i;in[i] =i; //中序遍历映射到0~n-1}//读入前序for(int i = 0; i<n; i++) {cin >> pre[i];pre[i] = pos[pre[i]];}build( 0, n-1, 0, n-1, 0);while(m--){int a, b;cin >> a >> b;if(pos.count(a) && pos.count(b)){a =pos[a],b= pos[b];int x =a, y =b;while(a != b){if(depth[a] > depth[b]) a =p[a];else b=p[b];}if(a != x && b!= y) printf("LCA of %d and %d is %d.\n",seq[x],seq[y],seq[a]);else if(a == x) printf("%d is an ancestor of %d.\n",seq[a],seq[y]);else  printf("%d is an ancestor of %d.\n",seq[a],seq[x]);}else if(pos.count(a) == 0 && pos.count(b) ==0) printf("ERROR: %d and %d are not found.\n",a,b);else if(pos.count(a) ==0)printf("ERROR: %d is not found.\n",a);else  printf("ERROR: %d is not found.\n",b);}
}