【PAT甲级题解记录】1151 LCA in a Binary Tree (30 分)

【PAT甲级题解记录】1151 LCA in a Binary Tree (30 分)

前言

Problem：1151 LCA in a Binary Tree (30 分)

Tags：树的遍历 并查集 LCA

Difficulty：剧情模式 想流点汗 想流点血 死而无憾

Address：1151 LCA in a Binary Tree (30 分)

问题描述

给定一棵二叉树，求两个元素 lowest common ancestor (LCA) 即最低公共祖先，也就是离两个元素的最近公共祖先节点。

解题思路

这道题至少可以有两种解法：

1. 暴力并查集法：利用并查集，说是并查集，其实只是一个保存前置节点的数组，在建树的过程中就可以得到。然后对输入的元素分别向上遍历，找到第一个相同的即可，但节点的值可以为负数，若存储下标也会超范围，所以我们需要离散化，可以自己写离散化，也可以利用map直接写（实测这道题需要unorder_map才不会超时）。
2. DFS建树法：结合建树过程（这种方法其实不用建树，但是与建树的递归逻辑重合），利用中序遍历数组的规律，当需要求的两个点分别在左右子树时则可确认当前分叉点就是LCA，否则就往两个点所在的子树dfs。可以参考柳：https://blog.csdn.net/liuchuo/article/details/82560863

排一个测试点2的坑，就是可能出现U=R的情况，此时应该输出U is an ancestor of V.

参考代码

1. 暴力并查集法

/** @Author: Retr0.Wu* @Date: 2022-02-20 00:29:21* @Last Modified by: Retr0.Wu* @Last Modified time: 2022-02-21 20:56:14*/
#include <bits/stdc++.h>
#include <unordered_map>  // 我的万能头不包含所以我加了
using namespace std;
int N, M;
vector<int> dep_v[10010]; // 每一层有哪些值
unordered_map<int, int> pre;
unordered_map<int, int> visit;
vector<int> in_order(10010);
vector<int> pre_order(10010);
int cnt;
vector<int> ansv;
vector<int> build(int prenumber, int in_l, int in_r, int pre_l, int pre_r)
{// 在in里找pre的第一个int pos = 0;for (int i = in_l; i <= in_r; i++){if (in_order[i] == pre_order[pre_l]){pos = i;break;}}pre[pre_order[pre_l]] = prenumber;//  左子树的大小  pos-in_lif (pos > in_l){// tree[2 * root + 1] = pre_order[pre_l + 1];vector<int> tv = build(pre_order[pre_l], in_l, pos - 1, pre_l + 1, pre_l + pos - in_l);}if (pos < in_r){// tree[2 * root + 2] = pre_order[pre_l + pos - in_l + 1];vector<int> tv = build(pre_order[pre_l], pos + 1, in_r, pre_l + pos - in_l + 1, pre_r);}return ansv;
}
int main()
{//cin >> M >> N;scanf("%d %d",&M,&N);for (int i = 0; i < N; i++){scanf("%d",&in_order[i]);}for (int i = 0; i < N; i++){scanf("%d",&pre_order[i]);}build(pre_order[0], 0, N - 1, 0, N - 1);for (int i = 0; i < M; i++){int U, V;cin >> U >> V;if (pre.count(U) == 0 && pre.count(V) == 0){printf("ERROR: %d and %d are not found.\n", U, V);}else if (pre.count(U) == 0){printf("ERROR: %d is not found.\n", U);}else if (pre.count(V) == 0){printf("ERROR: %d is not found.\n", V);}else{visit.clear(); // 每一次都是新的查找公共根，必须清空int m = U, n = V;int ans = 0;int flag = 1;// 俩个点分俩条路径往上遍历，找最近的共同遍历点while (m != pre[m]){visit[m] = 1;m = pre[m];}while(n!=pre[n]){if(visit[n]==1){ans = n;flag = 0;break;}n = pre[n];}if(flag) ans = m;  // 如果最终都没有找到除树根外的最近共同祖先，ans就只有可能是树根了if (ans == U){printf("%d is an ancestor of %d.\n", U, V);}else if (ans == V){printf("%d is an ancestor of %d.\n", V, U);}else{printf("LCA of %d and %d is %d.\n", U, V, ans);}}}return 0;
}

2. DFS建树法

#include<iostream>
#include<vector>
#include<map>
#include<cstdio>using namespace std;
int M;  // the number of pairs of nodes to be tested (1e3)
int N;  // the number of keys in the binary tree (1e4)
vector<int> pre_order, in_order;
map<int, int> pos;
int U, V;
int pos_U, pos_V; // U、V 在inorder中的位置
void init() {cin >> M >> N;in_order.resize(N), pre_order.resize(N);for (int i = 0; i < N; ++i) {cin >> in_order[i];pos[in_order[i]] = i;}for (int i = 0; i < N; ++i) cin >> pre_order[i];
}void creat_tree(int in_l, int in_r, int pre_l, int pre_r) {// find root in in_orderint pos_in = pos[pre_order[pre_l]];// LCA is found or U/V is an ancestor of anotherif ((pos_V < pos_in && pos_U > pos_in) || (pos_V > pos_in && pos_U < pos_in)) {printf("LCA of %d and %d is %d.\n", U, V, in_order[pos_in]);} else if (pos_U == pos_in) {printf("%d is an ancestor of %d.\n", U, V);} else if (pos_V == pos_in) {printf("%d is an ancestor of %d.\n", V, U);} else { // continue searchif (pos_U < pos_in && in_l < pos_in) {  // search leftcreat_tree(in_l, pos_in - 1, pre_l + 1, pre_l + (pos_in - in_l));}if (pos_U > pos_in && in_r > pos_in) {  // search rightcreat_tree(pos_in + 1, in_r, pre_l + (pos_in - in_l) + 1, pre_r);}}
}void test() {cin >> U >> V;// U/V is not foundif (pos.count(U) == 0 || pos.count(V) == 0) {if (pos.count(V) != 0) {printf("ERROR: %d is not found.\n", U);} else if (pos.count(U) != 0) {printf("ERROR: %d is not found.\n", V);} else {printf("ERROR: %d and %d are not found.\n", U, V);}return;}// LCA is found or U/V is an ancestor of anotherpos_V = pos[V], pos_U = pos[U];creat_tree(0, N - 1, 0, N - 1);
}void solution_1151() {init();for (int i = 0; i < M; i++) {test();}
}int main() {solution_1151();return 0;
}

总结

如果想要map速度不够，可以试试unordered_map。还是不行再考虑自己写映射离散化。