(PAT 1143) Lowest Common Ancestor (二叉查找树的LCA)

柔光的暖阳◎ 2022-04-23 08:32 145阅读 0赞

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.

解题思路:

这题根本就不用建树,根据二叉查找树的性质直接做就行了

遍历每一个结点(测试用例给出的是BST的先序,所以只需遍历数组即可),如果给出的两个结点一个在该节点的左边,一个在该结点的右边,那么这个结点就是两个结点的公共祖先

### 至于在左边右边,只需比较大小就行了！！！ ###

如果两个结点一个是另一个的祖先结点的情况,只需在遍历时把等于的情况考虑进去即可

就是这么简单

#include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;
    const int MAXN = 10100;
    int SDArray[MAXN];
    int main() {
    	int maxm = 0;
    	int minm = 0x7fffffff;
    	int N, M;
    	scanf("%d %d", &N, &M);
    	for (int i = 0; i < M; ++i) {
    		scanf("%d", &SDArray[i]);
    		if (SDArray[i] > maxm) maxm = SDArray[i];
    		if (SDArray[i] < minm) minm = SDArray[i];
    	}
    	for (int i = 0; i < N; ++i) {
    		int LA, LB;
    		scanf("%d %d", &LA, &LB);
    		if (LA > maxm || LA < minm || LB > maxm || LB < minm) {
    			if ((LA > maxm || LA < minm) && (LB > maxm || LB < minm)) {
    				printf("ERROR: %d and %d are not found.\n", LA, LB);
    			}
    			else if (LA > maxm || LA < minm) {
    				printf("ERROR: %d is not found.\n", LA);
    			}
    			else if (LB > maxm || LB < minm) {
    				printf("ERROR: %d is not found.\n", LB);
    			}
    			continue;
    		}
    		//LCA算法
    		for (int j = 0; j < M; ++j) {
    			if ((SDArray[j] >= LA && SDArray[j] <= LB) || (SDArray[j] >= LB && SDArray[j] <= LA)) {
    				if (SDArray[j] == LA) {
    					printf("%d is an ancestor of %d.\n", LA, LB);
    				}
    				else if (SDArray[j] == LB) {
    					printf("%d is an ancestor of %d.\n", LB, LA);
    				}
    				else {
    					printf("LCA of %d and %d is %d.\n", LA, LB, SDArray[j]);
    				}
    				break;
    			}
    		}
    	}
    
    	system("PAUSE");
    	return 0;
    }