PAT 1143 Lowest Common Ancestor（30 分）

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.

思路：先建树再从上到下搜索

程序：

#include <iostream> #include <cstdio> #include <vector> #include <unordered_map> #include <algorithm> using namespace std; struct node { int val; struct node* left; struct node* right; }; node* root = NULL; vector<int> vec; void createBST(node* &root,vector<int> &pre,vector<int> &mid,int pl,int pr,int ml,int mr) { if(pr < pl || mr < ml) return; int pos = ml; while(mid[pos] != pre[pl]) { pos++; } root = new node; root->val = pre[pl]; root->left = NULL; root->right = NULL; createBST(root->left,pre,mid,pl+1,pl+pos-ml,ml,pos-1); createBST(root->right,pre,mid,pl+pos-ml+1,pr,pos+1,mr); } /* 一开始的建树方法,一个节点一个节点地插到树上,有两个测试点超时 void createBST(node* &root,int val) { if(root == NULL) { root = new node; root->val = val; root->left = NULL; root->right = NULL; } else { if(val > root->val) createBST(root->right,val); else createBST(root->left,val); } } */ node* findLCA(node* root,int u,int v) { if((u >= root->val && v <= root->val) || (u <= root->val && v >= root->val)) return root; else { if(u < root->val && v < root->val) return findLCA(root->left,u,v); else if(u > root->val && v > root->val) return findLCA(root->right,u,v); } } int main() { int n,m; scanf("%d%d",&n,&m); unordered_map<int,bool> map; vector<int> mid; for(int i = 0; i < m; i++) { int val; scanf("%d",&val); vec.push_back(val); map[val] = true; } mid = vec; sort(mid.begin(),mid.end()); createBST(root,vec,mid,0,m-1,0,m-1); for(int i = 0; i < n; i++) { int u,v; scanf("%d%d",&u,&v); if(!map[u] && !map[v]) printf("ERROR: %d and %d are not found.\n",u,v); else if(!map[u]) printf("ERROR: %d is not found.\n",u); else if(!map[v]) printf("ERROR: %d is not found.\n",v); else { node* res = findLCA(root,u,v); if(res->val == u) { printf("%d is an ancestor of %d.\n",u,v); } else if(res->val == v) { printf("%d is an ancestor of %d.\n",v,u); } else { printf("LCA of %d and %d is %d.\n",u,v,res->val); } } } return 0; }