Data Structure Binary Tree: Lowest Common Ancestor in a Binary Tree

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 }