1143 Lowest Common Ancestor (30分)

思路一：根据先序序列依次将结点插入树中，之后对于给出的一对结点，分别找到两个结点从根到该结点的路径p1和p2。

#include<cstdio>
#include<vector>
using namespace std;

int queryNum, keyNum;

struct node {
	int val;
	node *left, *right;
	node(int v) {
		val = v;
		left = NULL;
		right = NULL;
	}
}*root;
void insert(node *&p, int val) {
	if (p == NULL) {
		p = new node(val);
		return;
	}
	if (val < p->val)
		insert(p->left, val);
	else insert(p->right, val);
}
int main() {
	scanf("%d %d", &queryNum, &keyNum);
	for (int i = 0;i < keyNum;i++) {
		int temp;
		scanf("%d", &temp);
		insert(root, temp);
	}
	for (int i = 0;i < queryNum;i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		vector<int> p1, p2;
		node *temp = root;
		while (temp != NULL) {
			p1.push_back(temp->val);
			if (temp->val == a)
				break;
			if (a < temp->val) {
				temp = temp->left;
			}
			else temp = temp->right;
		}
		temp = root;
		while (temp != NULL) {
			p2.push_back(temp->val);
			if (temp->val == b)
				break;
			if (b < temp->val) {
				temp = temp->left;
			}
			else temp = temp->right;
		}
		if (p1[p1.size() - 1] != a && p2[p2.size() - 1] != b) {
			printf("ERROR: %d and %d are not found.\n", a, b);
		}
		else if (p1[p1.size() - 1] != a) {
			printf("ERROR: %d is not found.\n", a);
		}
		else if (p2[p2.size() - 1] != b) {
			printf("ERROR: %d is not found.\n", b);
		}
		else {
			int index = 0;
			while (index < p1.size() && index < p2.size() && p1[index] == p2[index])
				index++;
			index--;
			if (p1[index] == a) {
				printf("%d is an ancestor of %d.\n", a, b);
			}
			else if (p1[index] == b) {
				printf("%d is an ancestor of %d.\n", b, a);
			}
			else {
				printf("LCA of %d and %d is %d.\n", a, b, p1[index]);
			}
		}
	}
}

两个测试点运行超时。考虑到结点数较多，不用每次插入一个结点的方式，而选择根据先序遍历的特点，借助栈进行建树，全部测试点通过：

#include<cstdio>
#include<vector>
#include<stack>
#include<cmath>
using namespace std;
vector<int> preorder;
int queryNum, keyNum;

struct node {
	int val;
	node *left, *right, *parent;
	node(int v) {
		val = v;
		left = NULL;
		right = NULL;
		parent = NULL;
	}
}*root;
void insert(node *&p, int val) {
	if (p == NULL) {
		p = new node(val);
		return;
	}
	if (val < p->val)
		insert(p->left, val);
	else insert(p->right, val);
}

bool isInsertPos(node *pos, int val) {
	while (pos->parent != NULL) {
		if (pos->parent->left == pos) {	//该结点是左子树
			if (abs(pos->parent->val) < abs(val))
				return false;
		}
		else {
			if (abs(pos->parent->val) > abs(val))
				return false;
		}
		pos = pos->parent;
	}
	return true;
}

int main() {
	scanf("%d %d", &queryNum, &keyNum);
	preorder.resize(keyNum);
	for (int i = 0;i < keyNum;i++) {
		scanf("%d", &preorder[i]);
	}

	//建树
	int index = 0;
	stack<node*> st;
	node *root = new node(preorder[index++]), *cur = root;
	st.push(root);
	while (index < preorder.size()) {
		while (index < preorder.size() && abs(preorder[index]) < abs(cur->val)) {
			cur->left = new node(preorder[index++]);
			cur->left->parent = cur;
			cur = cur->left;
			st.push(cur);
		}
		if (index < preorder.size()) {
			while (!isInsertPos(cur, preorder[index])) {
				cur = st.top();
				st.pop();
			}
			cur->right = new node(preorder[index++]);
			cur->right->parent = cur;
			cur = cur->right;
			st.push(cur);
		}
	}

	for (int i = 0;i < queryNum;i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		vector<int> p1, p2;
		node *temp = root;
		while (temp != NULL) {
			p1.push_back(temp->val);
			if (temp->val == a)
				break;
			if (a < temp->val) {
				temp = temp->left;
			}
			else temp = temp->right;
		}
		temp = root;
		while (temp != NULL) {
			p2.push_back(temp->val);
			if (temp->val == b)
				break;
			if (b < temp->val) {
				temp = temp->left;
			}
			else temp = temp->right;
		}
		if (p1[p1.size() - 1] != a && p2[p2.size() - 1] != b) {
			printf("ERROR: %d and %d are not found.\n", a, b);
		}
		else if (p1[p1.size() - 1] != a) {
			printf("ERROR: %d is not found.\n", a);
		}
		else if (p2[p2.size() - 1] != b) {
			printf("ERROR: %d is not found.\n", b);
		}
		else {
			int index = 0;
			while (index < p1.size() && index < p2.size() && p1[index] == p2[index])
				index++;
			index--;
			if (p1[index] == a) {
				printf("%d is an ancestor of %d.\n", a, b);
			}
			else if (p1[index] == b) {
				printf("%d is an ancestor of %d.\n", b, a);
			}
			else {
				printf("LCA of %d and %d is %d.\n", a, b, p1[index]);
			}
		}
	}
}

根据BST的特点，它的中序序列是有序的，则对于两个数u和v，如果先序序列的一个数preorder[i]满足以下关系：

v < preorder[i] < u, v < u
u < preorder[i] < v, u < v

即preorder[i]被夹在u和v之间，则说明preorder[i]已经是最低的公共祖先了，u和v分别在preorder[i]的左右子树中。
特殊情况是u和v其中之一就是那个根节点，这时u == preorder[i]或者v == preorder[i]。实现代码如下：

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
unordered_set<int> exist;
int main() {
	int m, n, u, v, a;
	scanf("%d %d", &m, &n);
	vector<int> preorder(n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &preorder[i]);
		exist.insert(preorder[i]);
	}
	for (int i = 0; i < m; i++) {
		scanf("%d %d", &u, &v);
		for (int j = 0; j < n; j++) {
			a = preorder[j];
			if ((a > u && a < v) || (a > v && a < u) || (a == u) || (a == v)) break;
		}
		if (exist.count(u) == 0 && exist.count(v) == 0)
			printf("ERROR: %d and %d are not found.\n", u, v);
		else if (exist.count(u) == 0 || exist.count(v) == 0)
			printf("ERROR: %d is not found.\n", exist.count(u) == 0 ? u : v);
		else if (a == u || a == v)
			printf("%d is an ancestor of %d.\n", a, a == u ? v : u);
		else
			printf("LCA of %d and %d is %d.\n", u, v, a);
	}
}