题目：
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..
Sample Input:
6 8
6 3 1 2 5 4 8 7
2 5
8 7
1 9
12 -3
0 8
99 99
Sample Output:
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.
思路：
1、利用二叉搜索树的性质和前序遍历建树，即通过中序遍历和前序遍历建树（二叉搜索树的中序遍历就是从小到大的排序）
2、然后开始前序遍历（假设需要找u,v两点的祖先）可以分为下面几个情况
①u和v在root的两侧，也就是一个大于root一个小于root那么root就是他们的共同祖先。
②若u，v都小于root那么进行遍历root的左子树，反之遍历其右子树。
③同时要判断u和v不存在的情况
3、测试点2，3段错误
因为key的值的范围为int，因此需要使用map或者unordered_map来表示key是否存在
代码：
#include<stdio.h> #include<map> using namespace std; int preorder[10005]; map<int, bool> f; int M, N; struct Node{ int x; Node* lchild; Node* rchild; }; Node* build(int left, int right){ if(left > right){ return NULL; } if(left == right){ Node* node = new Node; node -> x = preorder[left]; node -> lchild = NULL; node -> rchild = NULL; return node; } int k = right + 1; Node* node = new Node; node -> x = preorder[left]; for(int i = left + 1; i <= right; i++){ // 不要忘记考虑不存在preorder[i] > preorder[left]的情况，此时k未被赋值 if(preorder[i] > preorder[left]){ k = i; break; } } node -> lchild = build(left + 1, k - 1); node -> rchild = build(k, right); return node; } void find(Node* node, int x, int y){ if(x < node -> x && y < node -> x){ find(node -> lchild, x, y); }else if(x > node -> x && y > node -> x){ find(node -> rchild, x, y); }else if(node -> x == x){ printf("%d is an ancestor of %d.\n", x, y); return; }else if(node -> x == y){ printf("%d is an ancestor of %d.\n", y, x); return; } else{ printf("LCA of %d and %d is %d.\n", x, y, node -> x); return; } } int main(){ scanf("%d%d", &M, &N); for(int i = 1; i <= N; i++){ scanf("%d", &preorder[i]); f[preorder[i]] = true; } Node* root = build(1, N); for(int i = 0; i < M; i++){ int x, y; scanf("%d%d", &x, &y); if(!f[x] && !f[y]){ printf("ERROR: %d and %d are not found.\n", x, y); continue; }else if(!f[x] && f[y]){ printf("ERROR: %d is not found.\n", x); continue; }else if(f[x] && !f[y]){ printf("ERROR: %d is not found.\n", y); continue; } find(root, x, y); } return 0; }