-
Notifications
You must be signed in to change notification settings - Fork 0
/
leetcode_236.cpp
62 lines (54 loc) · 1.57 KB
/
leetcode_236.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
class Solution {
public:
bool getPath(TreeNode* root, TreeNode* p, vector<TreeNode*>& path){
if (!root) return false;
path.push_back(root);
bool found = false;
if(root->val == p->val) return true;
if (!found && root->left){
found = getPath(root->left, p, path);
}
if (!found && root->right){
found = getPath(root->right, p, path);
}
if(!found) path.pop_back();
return found;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<TreeNode*> path1;
vector<TreeNode*> path2;
getPath(root, p, path1);
getPath(root, q, path2);
TreeNode* ancestor;
int l1 = path1.size();
int l2 = path2.size();
for (int i = 0; i < l1 && i < l2; i++){
if (path1[i] == path2[i]){
ancestor = path1[i];
} else {
break;
}
}
return ancestor;
}
};
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == nullptr || p == root || q == root){
return root;
}
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if(left == nullptr && right == nullptr){
return nullptr;
}
if(left == nullptr){
return right;
}
if(right == nullptr){
return left;
}
return root;
}
};