题目
题目大意
给出一个二叉排序树的先序遍历，求U和V的最祖宗节点A。m是U和V的组数，n是二叉排序树的节点数。对于每一对U和V，如果U、V都存在且存在A是U、V的祖宗结点，那么输出LCA of U and V is A.；如果A是U和V的其中之一，输出X is an ancestor of Y.；如果U或V不存在，输出ERROR: U is not found. 或ERROR: V is not found.；如果U和V都不存在，输出ERROR: U and V are not found.
思路
不需要构造二叉排序树，直接根据二叉排序树的性质思考问题。这道题时间限制200ms，肯定要卡时间。第一点是U和V是否存在，这个不能通过遍历解决，否则肯定过不了，所以想到用map或unordered_map，直接通过节点名映射其是否存在，因此可以用map<int, bool>记录节点的存在与否。第二点是如何找到A，可以通过二叉排序树的性质解决。因为在二叉排序树中，根节点一定>=左子树，<=右子树，则A一定>=U且<=V，或>=V且<=U。先序遍历的顺序是根左右，所以从前往后遍历至找到满足条件的A。再根据题目条件输出即可。
代码
#include <iostream>
#include <vector>
#include <map>
using namespace std;int main(){int m, n;cin >> m >> n;vector<int> pos(n);map<int, bool> mp;for (int i = 0; i < n; i++){cin >> pos[i];mp[pos[i]] = true;}for (int i = 0; i < m; i++){int u, v;cin >> u >> v;int a;for (int j = 0; j < n; j++){a = pos[j];if (a >= u && a <= v || a >= v && a <= u){break;}}if (!mp[u] && !mp[v]){ // 如果mp中没有该元素，会将该元素插入键值对，其值为默认值false；如果怕插入多余元素，也可以用unordered_map，用里面的函数查找元素看是否存在printf("ERROR: %d and %d are not found.\n", u, v);}else if (!mp[u]){printf("ERROR: %d is not found.\n", u);}else if (!mp[v]){printf("ERROR: %d is not found.\n", v);}else if (a != u && a != v){printf("LCA of %d and %d is %d.\n", u, v, a);}else{printf("%d is an ancestor of %d.\n", a, a == u ? v : u);}}return 0;
}
/*
这道题的关键是利用二叉排序树的特性来解决问题，而不是直接构建树，再根据题目要求进行模拟。
其次就是用map判断元素是否被访问过，省去了遍历查找元素的过程。
有时候，简单题和复杂题只有一念之差。
*/
