1151 LCA in a Binary Tree 甲级

题意：

给定前序遍历和中序遍历，问u和v的lca
（先是中序，后是中序）

题解：

方法一：

参考题解
将树映射到一颗BST上，在BST上找到答案然后再映射回原本的树
方法二：
参考题解
已知某个树的根结点，若a和b在根结点的左边，则a和b的最近公共祖先在当前子树根结点的左子树寻找，如果a和b在当前子树根结点的两边，在当前子树的根结点就是a和b的最近公共祖先，如果a和b在当前子树根结点的右边，则a和b的最近公共祖先就在当前子树的右子树寻找。中序加先序可以唯一确定一棵树，在不构建树的情况下，在每一层的递归中，可以得到树的根结点，在此时并入lca算法可以确定两个结点的公共祖先～

代码：

#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);
            else
                printf("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);
        else
            printf("LCA of %d and %d is %d.\n", u, v, a);
    }
    return 0;
}

#include <iostream>
#include <vector>
#include <map>
using namespace std;
map<int, int> pos;
vector<int> in, pre;
void lca(int inl, int inr, int preRoot, int a, int b) {
    if (inl > inr) return;
    int inRoot = pos[pre[preRoot]], aIn = pos[a], bIn = pos[b];
    if (aIn < inRoot && bIn < inRoot)
        lca(inl, inRoot-1, preRoot+1, a, b);
    else if ((aIn < inRoot && bIn > inRoot) || (aIn > inRoot && bIn < inRoot))
        printf("LCA of %d and %d is %d.\n", a, b, in[inRoot]);
    else if (aIn > inRoot && bIn > inRoot)
        lca(inRoot+1, inr, preRoot+1+(inRoot-inl), a, b);
    else if (aIn == inRoot)
            printf("%d is an ancestor of %d.\n", a, b);
    else if (bIn == inRoot)
            printf("%d is an ancestor of %d.\n", b, a);
}
int main() {
    int m, n, a, b;
    scanf("%d %d", &m, &n);
    in.resize(n + 1), pre.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &in[i]);
        pos[in[i]] = i;
    }
    for (int i = 1; i <= n; i++) scanf("%d", &pre[i]);
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &a, &b);
        if (pos[a] == 0 && pos[b] == 0)
            printf("ERROR: %d and %d are not found.\n", a, b);
        else if (pos[a] == 0 || pos[b] == 0)
            printf("ERROR: %d is not found.\n", pos[a] == 0 ? a : b);
        else
            lca(1, n, 1, a, b);
    }
    return 0;
}