本文主要是介绍1151 LCA in a Binary Tree 一种自己的解法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
最近刷PAT的题目看到一个BST找最近共同祖先的新思路，大大化简了算法，给出链接：
https://blog.csdn.net/ysq96/article/details/81746996
因为这种解法只适合BST且需要先序排序，所以只能针对A1143这种题目，根据这个思路对于A1151我进行了算法的迁移使用：
将原来的树映射到一棵BST上，在BST上找到答案后映射回由原来的树，在此贴上代码。
#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <cstdio>
#include <map>using namespace std;int m, n;
int opre[10009], oin[10009];
int pre[10009], in[10009];
map<int, int> otos, stoo;int main()
{cin >> m >> n;for (int i = 0; i < n; i++){cin >> oin[i];otos[oin[i]] = i;stoo[i] = oin[i];}for (int i = 0; i < n; i++){cin >> opre[i];pre[i] = otos[opre[i]];}for (int i = 0; i < m; i++){int u, v;int a;bool flag1 = true, flag2 = true;cin >> u >> v;if (otos.find(u) == otos.end())flag1 = false;if (otos.find(v) == otos.end())flag2 = false;if (!flag1 || !flag2){if (!flag1 && !flag2)printf("ERROR: %d and %d are not found.\n", u, v);elseprintf("ERROR: %d is not found.\n", flag1 == false ? u : v);continue;}u = otos[u];v = otos[v];for (int j = 0; j < n; j++){a = pre[j];if (a > u && a < v || a < u && a > v || a == u || a == v)break;}u = stoo[u];v = stoo[v];a = stoo[a];if (a == u || a == v)printf("%d is an ancestor of %d.\n", a, a == u ? v : u);elseprintf("LCA of %d and %d is %d.\n", u, v, a);}return 0;
}
这篇关于1151 LCA in a Binary Tree 一种自己的解法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
