二叉搜索樹的最近公共祖先

題目描述
給定一棵二叉搜索樹的先序遍歷序列，要求你找出任意兩結點的最近公共祖先結點（簡稱 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.

二叉搜索樹性質

對于二叉搜索樹，我們規定任一結點的左子樹僅包含嚴格小于該結點的鍵值，而其右子樹包含大于或等于該結點的鍵值。如果我們交換每個節點的左子樹和右子樹，得到的樹叫做鏡像二叉搜索樹。

#include<bits/stdc++.h>
using namespace std;
//樹節點
struct tree
{int value;tree* left=NULL;tree* right=NULL;
};
//該節點是否存在
bool exist[10005];
int a[10005];
//插入節點建樹
//要利用二叉搜索樹的性質
tree* insert(int begin,int end)
{if(begin>end) return NULL;int rootValue=a[begin];tree* root=new tree;root->value=rootValue;//第一個比rootValue大的到結尾為右子樹int i;for(i=begin+1;i<=end;i++){if(a[i]>rootValue) break;}//遞歸root->left=insert(begin+1,i-1);root->right=insert(i,end);return root;
}
//找公共祖先節點LCA
int findpar(int u,int v,tree* root)
{while(1){if(root->value>u&&root->value>v) root=root->left;else if(root->value<u&&root->value<v) root=root->right;else break;}return root->value;
}
int main()
{int m,n;cin>>m>>n;//根節點tree* root=NULL;for(int i=0;i<n;i++){cin>>a[i];exist[a[i]]=1;}root=insert(0,n-1);for(int i=0;i<m;i++){int u,v;cin>>u>>v;//兩個節點都不存在if(!exist[u]&&!exist[v]){cout<<"ERROR: "<<u<<" and "<<v<<" are not found."<<endl;continue;}//一個節點不存在if(!exist[u]){cout<<"ERROR: "<<u<<" is not found."<<endl;continue;}if(!exist[v]){cout<<"ERROR: "<<v<<" is not found."<<endl;continue;}//兩個節點都存在bool flag=0;if(findpar(u,v,root)==u) cout<<u<<" is an ancestor of "<<v<<"."<<endl;else if(findpar(u,v,root)==v) cout<<v<<" is an ancestor of "<<u<<"."<<endl;else cout<<"LCA of "<<u<<" and "<<v<<" is "<<findpar(u,v,root)<<"."<<endl;}return 0;
}