PAT (Advanced Level) Practice 1143 Lowest Common Ancestor (30 分) 凌宸1642

题目描述：

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.

译：树中两个节点 U 和 V 的最低共同祖先 (LCA) 是将 U 和 V 作为后代的最深节点。

二叉搜索树 (BST) 递归地定义为具有以下属性的二叉树：

• 节点的左子树只包含键小于节点键的节点。

• 节点的右子树仅包含键大于或等于节点键的节点。

• 左右子树也必须是二叉搜索树。

给定 BST 中的任意两个节点，您应该找到它们的 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.

译：每个输入文件包含一个测试用例。 对于每种情况，第一行给出两个正整数： M (≤ 1,000)，要测试的节点对数； 和 N (≤ 10,000)，分别是 BST 中的密钥数量。 在第二行中，给出了 N 个不同的整数作为 BST 的前序遍历序列。 然后是 M 行，每行包含一对整数键 U 和 V。所有键都在 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..

译：对于每对给定的 U 和 V，如果找到 LCA 并且 A 是密钥，则在一行中打印 LCA of U and V is A. 。 但是如果 A 是 U 和 V 之一，则打印 X is an ancestor of Y. 。其中 X 是 A，Y 是另一个节点。 如果在 BST 中未找到 U 或 V，则在一行中打印 ERROR: U is not found. 或 ERROR: V is not found. 或 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.

The Idea：

• 思路其实很明确，但是就是在建树选择的结构上，如果选择链式指针，则倒数 测试点2 和测试点 3 会运行超时，所以只能选择静态的二叉树结构，由于每个节点的 key 的范围是int 内，所以需要建立一个 根节点 root 与其左右孩子节点的映射的静态 map 结构 。
• 思路：
  • 利用 中序 + 先序 建立二叉树
  • 利用 二叉搜索树的性质，查找指定的 u 和 v ：
    • 如果 u 和 v 两个节点，一个挂在root 的左子树，另一个挂在 root 的右子树 ，则最深的祖先节点就是 root
    • 如果 u 和 v 两个节点都挂在 root 的左子树上，则在 root 的左子树上查找。
    • 如果 u 和 v 两个节点都挂在 root 的右子树上，则在 root 的右子树上查找。

The Codes:

#include<bits/stdc++.h>
using namespace std ;
const int maxn = 10010 ;
struct node{
	int lchild , rchild ;
};
int pre[maxn] , in[maxn] ;

int m , n , t , u , v , ans ;
unordered_map<int , bool> mp ; // 利用map来静态建树，是可以借鉴的点 
unordered_map<int , node> tree ; // 如果直接使用 map 每次都会排序，则依旧会超时

int create(int preL , int  preR , int inL , int inR){
	if(preL > preR) return -1 ;
	int root = pre[preL] ;
	int k = inL ;
	for(; k <= inR ; k ++) if(in[k] == pre[preL]) break ;
	int numLeft = k - inL ;
	tree[root].lchild = create(preL + 1 , preL + numLeft , inL , k - 1) ;
	tree[root].rchild = create(preL + numLeft + 1 , preR , k + 1 , inR) ;
	return root ;
}
int search(int root , int u , int v){ 
	// 一个在root的左子树，另一个在root的右子树 
	if((u <= root && v >= root) || (v <= root && u >= root)) {
		return root ;	
	}
	// 都在 root 的左子树 
	if(u < root && v < root){
		return search(tree[root].lchild , u , v) ;
	}
	// 都在root 的右子树
	if(u > root && v > root){
		return search(tree[root].rchild , u , v) ;
	}
} 

int main(){
	scanf("%d%d" ,&m ,&n) ;
	for(int i = 0 ; i < n ; i ++){
		scanf("%d" ,&t) ;
		mp[t] = true ;
		pre[i] = in[i] = t ;
	}
	sort(in , in + n) ;
	int root = create(0 , n - 1 , 0 , n - 1) ;
	
	for(int i = 0 ; i < m ; i ++){
		scanf("%d%d" ,&u ,&v) ;
		if(mp.count(u) == 0 && mp.count(v) == 0)
			printf("ERROR: %d and %d are not found.\n" , u , v) ;
		else if(mp.count(u) == 0)
			printf("ERROR: %d is not found.\n" , u) ;
		else if(mp.count(v) == 0)
			printf("ERROR: %d is not found.\n" , v) ;
		else{
			ans = search(root , u , v) ;
			if(ans == u)  printf("%d is an ancestor of %d.\n" , u , v) ;
			else if(ans == v) printf("%d is an ancestor of %d.\n" , v , u) ;
			else printf("LCA of %d and %d is %d.\n" , u , v , ans) ;
		}
	}
	return 0 ;
}