题意：
给出一棵二叉搜索树的前序遍历，问结点u和v的共同最低祖先是谁，利用先序遍历特点。 二叉搜索树满足： 节点的左子树只包含键小于节点键的节点。 节点的键只包含节点的右键大于或等于子树的节点的键。 左子树和右子树也必须是二叉搜索树。
题解：
样例： 6 3 1 2 5 4 8 7 根据题目要求我们可以得到： 红字则是该数字在前序遍历中出现的顺序（从0开始） 我们可以从题目要求下手，在本题中，根的左子树总是小于根，右子树总是大于根 查询u和v的lca，如果一个x（x不与u和v重合）同时满足x>u,x<v,说明u在x的左边，v在x的右边，那说明x就是u和v的lca 同理。x<u,x>v也是 当然x和u或v重合时也是
代码：
#include<bits/stdc++.h>
using namespace std
;
map
<int,bool
> mp
;
int main(){
int m
,n
,u
,v
,a
;
cin
>>m
>>n
;
vector
<int> pre(n
);
for (int i
=0;i
<n
;i
++){
cin
>>pre
[i
];
mp
[pre
[i
]]=true
;
}
for (int i
=0;i
<m
;i
++)
{
cin
>>u
>>v
;
for (int j
=0;j
<n
;j
++)
{
a
=pre
[j
];
if ((a
>u
&&a
<v
)||(a
>v
&&a
<u
)||(a
==u
)||(a
==v
))break;
}
if (mp
[u
]==false
&&mp
[v
]==false
)
printf("ERROR: %d and %d are not found.\n",u
,v
);
else if (mp
[u
] == false
|| mp
[v
] == false
)
printf("ERROR: %d is not found.\n", mp
[u
] == false
? u
: v
);
else 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;
}
