题意：
给定前序遍历和中序遍历，问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;
}
