-
Notifications
You must be signed in to change notification settings - Fork 0
/
4_7.cpp
98 lines (88 loc) · 1.83 KB
/
4_7.cpp
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
89
90
91
92
93
94
95
//
// 4_7.cpp
// have parent node in node struct
//
// Created by Pengyan Qin on 6/27/15.
//
//
#include <iostream>
#include <unordered_map>
using namespace std;
struct node{ // declare the node
int data;
node* left;
node* right;
node* parent;
node() {}
node(int data_in):data(data_in), left(nullptr), right(nullptr){}
};
void insert(node* &root, node* parent, int dat){ // create BST
if(root == nullptr){
node *n = new node(dat);
n->parent = parent;
root = n;
return;
}
if(dat < root->data){
insert(root->left,root, dat);
}
else{
insert(root->right,root, dat);
}
}
void get_node(node* root, node* &store, int k){
if(root == nullptr)
return;
if(root->data == k){
store = root;
return;
}
get_node(root->left, store, k);
get_node(root->right, store, k);
}
// using hash table
node* commonAncestor(node *p, node *q){
if(p == q)
return p;
unordered_map<node*, int> map;
while(p){
map[p] = 1;
p = p->parent;
}
while(q){
if(map[q])
return q;
q = q->parent;
}
return nullptr;
}
// no additional storage
node* commonAncestor1(node *p, node *q){
if(p == q)
return p;
while(p){
p = p->parent;
node *t = q;
while(t){
t = t->parent;
if(t == p)
return p;
}
}
return nullptr;
}
int main(){
node *root = nullptr;
int a[]= {8, 3, 13, 1, 5, 9, 14, 16};
for(int i = 0; i < 8; ++i)
insert(root, nullptr, a[i]);
node *p;
node *q;
get_node(root, p, 9);
get_node(root, q, 16);
node* res = commonAncestor(p, q);
node* res1 = commonAncestor1(p, q);
cout << res->data << endl;
cout << res1->data << endl;
return 0;
}