pat 1151 LCA in a Binary Tree
起神解析很完善 暴力版
#include<bits/stdc++.h>
using namespace std;
const int maxsize = 10005;
struct Node {
int val, father, h;
Node(int v = -1, int h = 0, int father = -1): val(v), father(father), h(h) {};
} tree[maxsize];
int pre[maxsize], in[maxsize], m, n;
void createTree(int root, int l, int r, int father, int h) { // 构建树
if(l > r) return;
int i = l;
while(in[i] != pre[root]) i++;
tree[root] = Node(pre[root], h, father);
createTree(root + 1, l, i - 1, root, h + 1);
createTree(root + i - l + 1, i + 1, r, root, h + 1); // i这个位置左子树的数量 i - l, root + 左子树结点个数 + 1 为右根结点的位置
}
int main() {
scanf("%d%d", &m, &n);
for(int i = 0; i < n; i++) {
scanf("%d", &in[i]);
}
for(int i = 0; i < n; i++) {
scanf("%d", &pre[i]);
}
createTree(0, 0, n - 1 , -1, 0);
while(m--) {
int a, b, ia = -1, ib = -1;
scanf("%d%d", &a, &b); // a, b记录待交换的值
for(int i = 0; i < n; i++) {
if(tree[i].val == a) // ia = i记录树几点的下标索引位置
ia = i;
if(tree[i].val == b) // ib 记录树结点的下标索引位置
ib = i;
}
// 此处的判断
if(ia == -1 && ib == -1) {
printf("ERROR: %d and %d are not found.
", a, b);
} else if(ia == -1) {
printf("ERROR: %d is not found.
", a);
} else if(ib == -1) {
printf("ERROR: %d is not found.
", b);
} else {
bool ischange = false;
if(tree[ia].h < tree[ib].h) {
swap(ia, ib);
ischange = true;
}
while(tree[ia].h > tree[ib].h) {
ia = tree[ia].father;
}
if(tree[ia].val == tree[ib].val) {
printf("%d is an ancestor of %d.
", tree[ia].val, ischange ? b : a);
} else {
while(tree[ia].val != tree[ib].val) {
ia = tree[ia].father;
ib = tree[ib].father;
}
printf("LCA of %d and %d is %d.
", a, b, tree[ia].val);
}
}
}
return 0;
}
LCA方法:
关键代码：
优质博客：https://blog.csdn.net/Q_M_X_D_D_/article/details/90047735
fa[i][j] //表示从编号为i的结点跳 2 的j 次方层所到达的结点
至于如何求出i结点可以跳到的结点， 运用递推式 fa[i][j] = fa[fa[i][j - 1]][j - 1],(也可以理解为 2的j次方 = 2的j -1 次方 + 2的 j - 1次方) 从根节点最上层执行，初始条件是 , fa[i][0] = father; 其中 j 能取到的最大值是 (1 << j) <= dep[i] // dep[i]表示树的高度
#include<bits/stdc++.h>
using namespace std;
const int maxsize = 10005;
int pre[maxsize], in[maxsize], dep[maxsize], fa[maxsize][20];
bool f = false; // 判断是否以及交换
void dfs(int root, int father, int l, int r) {
if(l > r) return;
dep[root] = dep[father] + 1;
fa[root][0] = father;
for(int i = 1; (1 << i) <= dep[root]; i++) {
fa[root][i] = fa[fa[root][i - 1]][i - 1];
}
int i = l;
while(in[i] != pre[root]) i++;
dfs(root + 1, root, l, i - 1);
dfs(root + (i - l) + 1, root, i + 1, r);
}
void LCA(int ia, int ib, int a, int b) {
for(int i = 19; i >= 0; i--) {
if(dep[ia] - (1 << i) >= dep[ib])
ia = fa[ia][i];
}
if(ia == ib) printf("%d is an ancestor of %d.
", pre[ia], f ? b : a);
else {
for(int i = 19; i >= 0 ; i--) {
if(fa[ia][i] != fa[ib][i]) {
ia = fa[ia][i];
ib = fa[ib][i];
}
}
printf("LCA of %d and %d is %d.
", a, b, pre[fa[ia][0]]);
}
}
int main() {
int m, n;
scanf("%d%d", &m, &n);
for(int i = 0; i < n; i++) {
scanf("%d", &in[i]);
}
for(int i = 0; i < n; i++) {
scanf("%d", &pre[i]);
}
dfs(0, 0, 0, n - 1);
while(m--) {
int a, b, ia = -1, ib = -1;
scanf("%d%d", &a, &b);
for(int i = 0; i < n; i++) {
if(a == pre[i]) ia = i;
if(b == pre[i]) ib = i;
}
if(ia == -1 && ib == -1) {
printf("ERROR: %d and %d are not found.
", a, b);
} else if(ia == -1) {
printf("ERROR: %d is not found.
", a);
} else if(ib == -1) {
printf("ERROR: %d is not found.
", b);
} else {
f = false;
if(dep[ia] < dep[ib]) {
swap(ia, ib);
f = true;
}
LCA(ia, ib, a, b);
}
}
return 0;
}