241348 - 二叉搜索树的最近共同祖先(LCA)

题目描述

给定一个由 n 个整数构建的二叉搜索树(BST),输入两个整数 q 和 p,请找出这两个节点的最近共同祖先(LCA)。若有一个节点不存在于树中,则输出 -1;

输入

第一行输入整数 n(1 ≤ n ≤ 1000)。 第二行输入 n 个整数,表示二叉搜索树的节点值(输入顺序任意,可能包含重复值,重复值按 BST 规则插入到右子树)。 第三行输入两个整数 q 和 p。

输出

输出 q 和 p 的最近共同祖先的值,若任意节点不存在则输出 -1。

样例

输入

5  
6 2 8 1 4  
1 4  

输出

2  

输入

3  
8 3 10  
2 3

输出

-1 
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 27
通过人数 17
金币数量 2 枚
难度 基础


上一题 下一题