1143 Lowest Common Ancestor 甲级
程序员文章站
2022-07-14 14:51:43
...
题意:
给出一棵二叉搜索树的前序遍历,问结点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;
}
推荐阅读
-
PAT甲级1143 Lowest Common Ancestor BST+LCA
-
1143 Lowest Common Ancestor 甲级
-
[C++] PAT 1143 Lowest Common Ancestor (30分)
-
⭐⭐⭐⭐⭐PAT A1143 Lowest Common Ancestor
-
PAT 1143 Lowest Common Ancestor 【C++版】
-
1143 Lowest Common Ancestor
-
pat-1143 Lowest Common Ancestor (30分)
-
1143 Lowest Common Ancestor (30分)
-
1143 Lowest Common Ancestor (30分)
-
LeetCode 236 -- 二叉树的最近公共祖先 ( Lowest Common Ancestor of a Binary Tree ) ( C语言版 )