PATa1143

目的：找到两个节点的最低祖先。在二叉搜索树上找

输入：

M  被测试的节点对数 1000

N  二叉搜索树的节点个数 10000

然后给出二叉搜索树的先序遍历序列

然后再是M个节点对。每对节点有U,V两个节点。

输出：

如果找到了LCA，输出"LCA of U and V is A."

如果LCA是U和V中的一个，输出"X is an ancestor of Y."

如股票没有找到：

可能是因为点不在树中；

输出：ERROR: U is not found. 

           ERROR: V is not found. 

           ERROR: U and V are not found.

算法：

根据二叉搜索树的特点，若是两个节点的最小根节点。那么这个节点的值一定处于两个之间，而且，一定在两个节点之前。

判断在不在树中，用一个map存一下，查找看在不在。

#include<stdio.h> #include<map> #include<math.h> using namespace std; const int maxn = 10010; int a[maxn]; map<int,int> b; int n,m; int main() { scanf("%d%d",&m,&n); for(int i=0;i<n;i++) { scanf("%d",&a[i]); b[a[i]] = 1; } for(int i=0;i<m;i++) { int u,v; scanf("%d%d",&u,&v); if(b.find(u)==b.end()&&b.find(v)==b.end()) { printf("ERROR: %d and %d are not found.\n",u,v); }else if(b.find(u)==b.end()) { printf("ERROR: %d is not found.\n",u); }else if(b.find(v)==b.end()) { printf("ERROR: %d is not found.\n",v); }else { int ans; for(int j=0;j<n;j++) { if(a[j]>min(u,v)&&a[j]<=max(u,v)) { ans = a[j]; break; } } if(ans==u||ans==v) { printf("%d is an ancestor of %d.\n",ans,ans==u?v:u); }else { printf("LCA of %d and %d is %d.\n",u,v,ans); } } } return 0; }

反思：最后一些困难，是狭隘得理解了根节点一定在中间，所以我认为，根节点一定大于左边节点，小于等于右边节点，事实上，这两个节点中可能有根节点，所以两边都有等于。