1151 LCA in a Binary Tree (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.
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:
1 | 6 8 |
Sample Output:
1 | LCA of 2 and 6 is 3. |
作者: CHEN, Yue
单位: 浙江大学
时间限制: 1000 ms
内存限制: 64 MB
代码长度限制: 16 KB
题目大意
给出一棵二叉树的前中序遍历，要求判断给定两个结点的最近公共祖先
分析
类似1143 Lowest Common Ancestor (30 分)，但是因为不是二叉搜索树，所以不能那样做。
可以dfs记录路径，然后判断路径上出现分叉的点。
或者递归在左右子树中查找。lca在root中寻找a,b。如果root对应结点等于a或b，返回当前结点。否则在左右子树中查找a,b。左右都找到了返回当前结点，如果仅在一边找到那么返回找到的那一个子树。
代码
dfs代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
using namespace std;
int n,m,a,b,found;
vector<int> pre,in,patha,pathb,temp;
struct node{
int x;
node* left;
node* right;
};
node* root;
node* buildtree(int ins,int ine,int pres,int pree){
if(ins>=ine||pres>=pree)
return nullptr;
node* cur=new node;
cur->x=pre[pres];
int i=ins;
while(in[i]!=pre[pres])i++;
cur->left=buildtree(ins, i, pres+1, pres+i-ins+1);
cur->right=buildtree(i+1, ine, pres+i-ins+1, pree);
return cur;
}
void dfs(node* cur,int val,int a){
if(found)
return;
if(cur->x==val){
found=1;
temp.push_back(val);
if(a==1)
patha=temp;
else
pathb=temp;
}
temp.push_back(cur->x);
if(cur->left!=nullptr)
dfs(cur->left,val,a);
if(cur->right!=nullptr)
dfs(cur->right,val,a);
temp.pop_back();
return;
}
int main() {
cin>>m>>n;
pre.resize(n);
in.resize(n);
for(int i=0;i<n;i++)
cin>>in[i];
for(int i=0;i<n;i++)
cin>>pre[i];
root=buildtree(0, n, 0, n);
for(int i=0;i<m;i++){
cin>>a>>b;
temp.clear();
patha.clear();
found=0;
dfs(root, a, 1);
found=0;
temp.clear();
pathb.clear();
dfs(root, b, 0);
if(patha.size()==0||pathb.size()==0){
if(patha.size()==0&&pathb.size()==0)
printf("ERROR: %d and %d are not found.\n",a,b);
else if(patha.size()==0)
printf("ERROR: %d is not found.\n",a);
else
printf("ERROR: %d is not found.\n",b);
}else{
int i=0;
for(;i<patha.size()&&i<pathb.size();i++){
if(patha[i]!=pathb[i])
break;
}
if(i==patha.size())
printf("%d is an ancestor of %d.\n",a,b);
else if(i==pathb.size())
printf("%d is an ancestor of %d.\n",b,a);
else
printf("LCA of %d and %d is %d.\n",a,b,patha[i-1]);
}
}
return 0;
}
递归代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
using namespace std;
int n,m,a,b;
vector<int> pre,in;
struct node{
int x;
node* left;
node* right;
};
node* root;
node* buildtree(int ins,int ine,int pres,int pree){
if(ins>=ine||pres>=pree)
return nullptr;
node* cur=new node;
cur->x=pre[pres];
int i=ins;
while(in[i]!=pre[pres])i++;
cur->left=buildtree(ins, i, pres+1, pres+i-ins+1);
cur->right=buildtree(i+1, ine, pres+i-ins+1, pree);
return cur;
}
node* lca(node* root,int a,int b){
if(root==nullptr)
return nullptr;
if(root->x==a||root->x==b) return root;
node* left=lca(root->left,a,b);
node* right=lca(root->right,a,b);
if(left&&right)
return root;
return left==nullptr?right:left;
}
int main() {
cin>>m>>n;
pre.resize(n);
in.resize(n);
for(int i=0;i<n;i++)
cin>>in[i];
for(int i=0;i<n;i++)
cin>>pre[i];
root=buildtree(0, n, 0, n);
for(int i=0;i<m;i++){
cin>>a>>b;
int fda=0,fdb=0;
for(int i=0;i<n;i++){
if(a==in[i])
fda=1;
if(b==in[i])
fdb=1;
if(fda&&fdb)
break;
}
if(!fda||!fdb){
if(!fda&&!fdb)
printf("ERROR: %d and %d are not found.\n",a,b);
else if(!fda)
printf("ERROR: %d is not found.\n",a);
else
printf("ERROR: %d is not found.\n",b);
}else{
node* temp=lca(root,a,b);
if(temp->x==a||temp->x==b)
printf("%d is an ancestor of %d.\n",temp->x==a?a:b,temp->x==a?b:a);
else
printf("LCA of %d and %d is %d.\n",a,b,temp->x);
}
}
return 0;
}