http://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
#include <queue>
5
#include <stack>
6
#include <
string
>
7
#include <fstream>
8
#include <map>
9
using
namespace
std;
10
11
struct
node {
12
int
data;
13
struct
node *left, *
right;
14
node() : data(
0
), left(NULL), right(NULL) { }
15
node(
int
d) : data(d), left(NULL), right(NULL) { }
16
};
17
18
bool
findpath(node *root, vector<
int
> &path,
int
n) {
19
if
(!root)
return
false
;
20
path.push_back(root->
data);
21
if
(root->data == n)
return
true
;
22
if
(root->left && findpath(root->left, path, n) || root->right && findpath(root->right, path, n))
return
true
;
23
path.pop_back();
24
return
false
;
25
}
26
27
int
LCA(node *root,
int
n1,
int
n2) {
28
if
(!root)
return
-
1
;
29
vector<
int
>
path1, path2;
30
if
(!findpath(root, path1, n1) || !findpath(root, path2, n2))
return
-
1
;
31
int
i =
0
;
32
for
(; i < path1.size() && i < path2.size(); i++
) {
33
if
(path1[i] != path2[i])
break
;
34
}
35
return
path1[i-
1
];
36
}
37
38
int
main() {
39
node *root =
new
node(
1
);
40
root->left =
new
node(
2
);
41
root->right =
new
node(
3
);
42
root->left->left =
new
node(
4
);
43
root->left->right =
new
node(
5
);
44
root->right->left =
new
node(
6
);
45
root->right->right =
new
node(
7
);
46
cout <<
"
LCA(4, 5) is
"
<< LCA(root,
4
,
5
) <<
endl;
47
cout <<
"
LCA(4, 6) is
"
<< LCA(root,
4
,
6
) <<
endl;
48
cout <<
"
LCA(3, 4) is
"
<< LCA(root,
3
,
4
) <<
endl;
49
cout <<
"
LCA(2, 4) is
"
<< LCA(root,
2
,
4
) <<
endl;
50
return
0
;
51
}
one traversal
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
#include <queue>
5
#include <stack>
6
#include <
string
>
7
#include <fstream>
8
#include <map>
9
using
namespace
std;
10
11
struct
node {
12
int
data;
13
struct
node *left, *
right;
14
node() : data(
0
), left(NULL), right(NULL) { }
15
node(
int
d) : data(d), left(NULL), right(NULL) { }
16
};
17
18
node* LCA(node *root,
int
n1,
int
n2) {
19
if
(!root)
return
NULL;
20
if
(root->data == n1 || root->data == n2)
return
root;
21
node *l = LCA(root->
left, n1, n2);
22
node *r = LCA(root->
right, n1, n2);
23
if
(l && r)
return
root;
24
return
l?
l : r;
25
}
26
27
int
main() {
28
node *root =
new
node(
1
);
29
root->left =
new
node(
2
);
30
root->right =
new
node(
3
);
31
root->left->left =
new
node(
4
);
32
root->left->right =
new
node(
5
);
33
root->right->left =
new
node(
6
);
34
root->right->right =
new
node(
7
);
35
cout <<
"
LCA(4, 5) is
"
<< LCA(root,
4
,
5
)->data <<
endl;
36
cout <<
"
LCA(4, 6) is
"
<< LCA(root,
4
,
6
)->data <<
endl;
37
cout <<
"
LCA(3, 4) is
"
<< LCA(root,
3
,
4
)->data <<
endl;
38
cout <<
"
LCA(2, 4) is
"
<< LCA(root,
2
,
4
)->data <<
endl;
39
return
0
;
40
}
上面这段代码有些问题，当n1或者n2不存在时应该回NULL，但是回的是n1或者n2
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
#include <queue>
5
#include <stack>
6
#include <
string
>
7
#include <fstream>
8
#include <map>
9
using
namespace
std;
10
11
struct
node {
12
int
data;
13
struct
node *left, *
right;
14
node() : data(
0
), left(NULL), right(NULL) { }
15
node(
int
d) : data(d), left(NULL), right(NULL) { }
16
};
17
18
node* _LCA(node *root,
int
n1,
int
n2,
bool
&v1,
bool
&
v2) {
19
if
(!root)
return
NULL;
20
if
(root->data ==
n1) {
21
v1 =
true
;
22
return
root;
23
}
24
if
(root->data ==
n2) {
25
v2 =
true
;
26
return
root;
27
}
28
node *l = _LCA(root->
left, n1, n2, v1, v2);
29
node *r = _LCA(root->
right, n1, n2, v1, v2);
30
if
(l && r)
return
root;
31
return
l?
l : r;
32
}
33
34
bool
findnode(node *root,
int
k) {
35
if
(!root)
return
false
;
36
return
(root->data == k || findnode(root->left, k) || findnode(root->
right, k));
37
}
38
39
node *LCA(node *root,
int
n1,
int
n2) {
40
bool
v1 =
false
;
41
bool
v2 =
false
;
42
node *lca =
_LCA(root, n1, n2, v1, v2);
43
if
(v1 && v2 || v1 && findnode(root, n2) || v2 && findnode(root, n1))
return
lca;
44
return
NULL;
45
}
46
47
int
main() {
48
node *root =
new
node(
1
);
49
root->left =
new
node(
2
);
50
root->right =
new
node(
3
);
51
root->left->left =
new
node(
4
);
52
root->left->right =
new
node(
5
);
53
root->right->left =
new
node(
6
);
54
root->right->right =
new
node(
7
);
55
cout <<
"
LCA(4, 5) is
"
<< LCA(root,
4
,
5
)->data <<
endl;
56
cout <<
"
LCA(4, 6) is
"
<< LCA(root,
4
,
6
)->data <<
endl;
57
cout <<
"
LCA(3, 4) is
"
<< LCA(root,
3
,
4
)->data <<
endl;
58
cout <<
"
LCA(2, 4) is
"
<< LCA(root,
2
,
4
)->data <<
endl;
59
return
0
;
60
}
Data Structure Binary Tree: Lowest Common Ancestor in a Binary Tree
