# 题目

The lowest common ancestor (LCA) of two nodes U and V in a tree is the deepest node that has both U and V as descendants.

A binary search tree (BST) is recursively defined as a binary tree which has the following properties:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
• Both the left and right subtrees must also be binary search trees.

Given any two nodes in a BST, you are supposed to find their LCA.

### Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers: M (≤ 1,000), the number of pairs of nodes to be tested; and N (≤ 10,000), the number of keys in the BST, respectively. In the second line, N distinct integers are given as the preorder traversal sequence of the BST. Then M lines follow, each contains a pair of integer keys U and V. All the keys are in the range of int.

### Output Specification:

For each given pair of U and V, print in a line `LCA of U and V is A.` if the LCA is found and `A` is the key. But if `A` is one of U and V, print `X is an ancestor of Y.` where `X` is `A` and `Y` is the other node. If U or V is not found in the BST, print in a line `ERROR: U is not found.` or `ERROR: V is not found.` or `ERROR: U and V are not found.`.

# 题解

## 思路

• 题目给定了一棵二叉搜索树，然后给你两个节点，求它们的最近的公共上级
• 给定的树是以中序遍历的形式给出的
• 这个中序遍历和二叉搜索树是重点
• 因为是前序遍历，就是根左右，所以根的大小就在左右大小之间。
• 所以我们只要遍历前序遍历，找到第一个在两个节点中间的点，便是它们的公共上级。

## 数据结构

• pre 是前序遍历
• sets 是所有节点的集合

## 算法

• 先判断u和v是不是在节点中
• 然后遍历前序遍历
• 当找到了一个在两个节点大小中间的节点的时候，它就是根。

## 代码

• Python会有一个点超时。放了C++和Python的题解。