发门网
二叉搜索树的最近公共祖先
创始人
2024-04-22 12:19:48
0次

题目描述

给定一棵二叉搜索树的先序遍历序列，要求你找出任意两结点的最近公共祖先结点（简称 LCA）。

输入

输入的第一行给出两个正整数：待查询的结点对数 M（≤ 1 000）和二叉搜索树中结点个数 N（≤ 10 000）。随后一行给出 N 个不同的整数，为二叉搜索树的先序遍历序列。最后 M 行，每行给出一对整数键值 U 和 V。所有键值都在整型int范围内。

输出

对每一对给定的 U 和 V，如果找到 A 是它们的最近公共祖先结点的键值，则在一行中输出 LCA of U and V is A.。但如果 U 和 V 中的一个结点是另一个结点的祖先，则在一行中输出 X is an ancestor of Y.，其中 X 是那个祖先结点的键值，Y 是另一个键值。如果 二叉搜索树中找不到以 U 或 V 为键值的结点，则输出 ERROR: U is not found. 或者 ERROR: V is not found.，或者 ERROR: U and V are not found.。

输入样例1 

6 8
6 3 1 2 5 4 8 7
2 5
8 7
1 9
12 -3
0 8
99 99

输出样例1

LCA of 2 and 5 is 3.
8 is an ancestor of 7.
ERROR: 9 is not found.
ERROR: 12 and -3 are not found.
ERROR: 0 is not found.
ERROR: 99 and 99 are not found.

AC代码

#include
#include
#include
using namespace std;
struct Node {int data;Node *left = NULL;Node *right = NULL;
};class BST {mapancestor;
public:Node *root = NULL;void Insert(int &data) {Node *newOne = new Node();newOne->data = data;if (root == NULL) {root = newOne;return;}Node *current = root;while (current) {if (current->data > data) {if (current->left)current = current->left;else {current->left = newOne;ancestor[data]=current->data;return;}} else {if (current->right)current = current->right;else {current->right = newOne;ancestor[data]=current->data;return;}}}}bool IsAncestor(int&a,int&b){for(auto&[child,parent]:ancestor)if(child==a&&parent==b){cout<current->data&&b>current->data)return FindBingo(a,b,current->right);else if(adata&&bdata)return FindBingo(a,b,current->left);return current->data;}
};int main() {int m,n, temp,U,V;BST test;setdata;cin >>m>> n;while (n--) {cin >> temp;data.insert(temp);test.Insert(temp);}while(m--){cin>>U>>V;if(data.find(U)==data.end()&&data.find(V)==data.end()){cout<<"ERROR: "<
词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：I2C总线式驱动开发

下一篇：React学习2（面向组件编程）

相关内容

热门资讯

监控摄像头接入GB28181平... 流程简介将监控摄像头的视频在网站和APP中直播，要解决的几个问题是：1&...
Windows10添加群晖磁盘... 在使用群晖NAS时，我们需要通过本地映射的方式把NAS映射成本地的一块磁盘使用。 通过...
protocol buffer... 目录 目录 什么是protocol buffer 1.protobuf 1.1安装  1.2使用...
在Word、WPS中插入AxM... 引言 我最近需要写一些文章，在排版时发现AxMath插入的公式竟然会导致行间距异常&#...
【PdgCntEditor】解... 一、问题背景 大部分的图书对应的PDF，目录中的页码并非PDF中直接索引的页码...
Fluent中创建监测点 1 概述某些仿真问题，需要创建监测点，用于获取空间定点的数据࿰...
educoder数据结构与算法...                                                   ...
MySQL下载和安装（Wind... 前言：刚换了一台电脑，里面所有东西都需要重新配置，习惯了所...
修复 爱普生 EPSON L4... L4151 L4153 L4156 L4158 L4163 L4165 L4166 L4168 L4...
MFC文件操作  MFC提供了一个文件操作的基类CFile，这个类提供了一个没有缓存的二进制格式的磁盘...