题目描述
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.
Given any two nodes in a binary tree, 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 binary tree, respectively. In each of the following two lines, N distinct integers are given as the inorder and preorder traversal sequences of the binary tree, respectively. It is guaranteed that the binary tree can be uniquely determined by the input sequences. 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 binary tree, 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
7 2 3 4 6 5 1 8
5 3 7 2 6 4 8 1
2 6
8 1
7 9
12 -3
0 8
99 99
Sample Output:
LCA of 2 and 6 is 3.
8 is an ancestor of 1.
ERROR: 9 is not found.
ERROR: 12 and -3 are not found.
ERROR: 0 is not found.
ERROR: 99 and 99 are not found.
考点
1.两种遍历可以唯一地确定一棵树；
2.如何追溯最小公共父结点。
思路
1.需要建树吗？
先序遍历输出的是每个根结点，中序遍历可以确定结点的相对位置。因此不需要建树就可以得知两个结点的相对关系。
2.递归实现
判断根结点与两个结点的相对位置关系，如果两个结点都在根结点的左边，那么它们的最小公共父结点一定在根节点的左子树上；在右边的情况类似。如果分别位居左右，那么这个根节点就是两个结点的最小父结点。
3.具体实现
(1)需要一个pos记录每个输入结点的相对位置，这样便于进行相对位置的比较，同时也有助于判断输入结点是否在这棵树中；
(2)pos的数据类型选择使用map，键值对有助于查询，同时map的int类型默认值为0；
(3)在每次判别之后都需要对查询范围以及根结点的值进行更新，查询范围[s, e]根据定位进行缩小，如果在左边那么范围更新为[s, root-1]，在右边则更新为[root+1, e]。
根结点的值根据先序遍历preOrder的输出变化，初始值即为先序遍历第一个值key=1，此后如果在根结点的左边，那么下一个根结点为key=key+1；由于先序遍历的遍历顺序为：根、左、右，在遍历右子树之前一定遍历完了左子树，因此如果在根结点的右边，那么下一个根结点为key=key+1+(root-s)，跳过左子树的部分以减少时耗。
代码
#include <iostream>
#include <vector>
#include <map>
using namespace std;
vector<int> inOrder, preOrder;
map<int, int> pos;
void LCA(int s, int e, int key, int a, int b) {
if (s > e) {
return;
}
int inRoot = pos[preOrder[key]], aIn = pos[a], bIn = pos[b];
if (aIn < inRoot&&bIn < inRoot) {
LCA(s, inRoot - 1, key+1, a, b);
}
else if (aIn > inRoot&&bIn > inRoot) {
LCA(inRoot + 1, e, key + 1+(inRoot-s), a, b);
}
else if ((aIn<inRoot&&bIn>inRoot) || (bIn<inRoot&&aIn>inRoot)) {
cout << "LCA of " << a << " and " << b << " is " << inOrder[inRoot] << "." << endl;
}
else if (aIn == inRoot) {
cout << a << " is an ancestor of " << b << "." << endl;
}
else if (bIn = inRoot) {
cout << b << " is an ancestor of " << a << "." << endl;
}
}
int main() {
int M, N;
cin >> M;cin >> N;
inOrder.resize(N+1);preOrder.resize(N+1);
for (int i = 1; i <= N; i++) {
cin >> inOrder[i];
pos[inOrder[i]] = i;
}
for (int i = 1; i <= N; i++) {
cin >> preOrder[i];
}
//test
for (int i = 0; i < M; i++) {
int a, b;
cin >> a;
cin >> b;
if (pos[a] == 0&&pos[b]==0) {
cout << "ERROR: " << a << " and " << b << " are not found." << endl;
}
else if (pos[a] == 0||pos[b] == 0) {
cout << "ERROR: " << (pos[a] == 0 ? a : b) << " is not found." << endl;
}
else {
LCA(1, N, 1, a, b);
}
}
return 0;
}
