1143 Lowest Common Ancestor（30 分）

代码与解析来自：https://blog.csdn.net/lv1224/article/details/79605263

这道题考察的是搜索二叉树的最低公共祖先，算是一道比较经典的题目了。题目给出了BST的前序遍历，而前序遍历升序排列就是BST的中序遍历了。由前序遍历和中序遍历就可以确定唯一一棵二叉树了。
创建一棵二叉树以后，同时深度搜索U和V，如果出现当前节点等于U或者V，则找到公共祖先。或者U和V分别位于节点node的左右子树，则node为最低公共祖先 +

注意两点：只能用中序和前序建树，直接插入建树会超时，还有就是使用map标记访问，int型数组可能会超

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
struct node {
    int data;
    node *rchild, *lchild;
};
const int maxn = 1e4 + 10;
int pre[maxn], in[maxn], n, m;
map<int, bool>mp;
node* create(int preL, int preR, int inL, int inR)
{
    if (preL > preR)return NULL;
    node* root = new node;
    root->data = pre[preL];
    int k;
    for (k = inL; k <= inR; k++)
    {
        if (in[k] == root->data)break;
    }
    int numleft = k - inL;
    root->lchild = create(preL + 1, preL + numleft, inL, k - 1);
    root->rchild = create(preL + numleft + 1, preR, k + 1, inR);
    return root;
}
void findances(node* root, int x, int y)
{
    if (root == NULL)return;
    if (root->data == x)
    {
        printf("%d is an ancestor of %d.\n", x, y);
        return;
    }
    if (root->data == y)
    {
        printf("%d is an ancestor of %d.\n", y,x);
        return;
    }
    if ((x > root->data&&y < root->data)||(x<root->data&&y>root->data))
    {
        printf("LCA of %d and %d is %d.\n", x, y, root->data);
        return;
    }
    if (x < root->data&&y < root->data)findances(root->lchild, x, y);
    else if (x > root->data&&y > root->data)findances(root->rchild, x, y);
}
int main()
{
    scanf("%d%d", &m, &n);
    for (int i = 0; i < n; i++)scanf("%d", &pre[i]), in[i] = pre[i], mp[in[i]] = true;
    sort(in, in + n);
    node* root = NULL;
    root = create(0, n - 1, 0, n - 1);
    while (m--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        if (mp[x] == false || mp[y] == false)
        {
            if (mp[x] == false && mp[y] == false)printf("ERROR: %d and %d are not found.\n", x, y);
            else if (mp[x] == false)printf("ERROR: %d is not found.\n", x);
            else if (mp[y] == false)printf("ERROR: %d is not found.\n", y);
            continue;
        }
        findances(root, x, y);
    }
    return 0;
}