8000 lowest_common_ancestor · hitzzc/go-leetcode@f9c8c63 · GitHub
[go: up one dir, main page]
Skip to content

Commit f9c8c63

Browse files
hitzzchitzzc
committed
lowest_common_ancestor
1 parent 041262e commit f9c8c63

File tree

3 files changed

+67
-0
lines changed

3 files changed

+67
-0
lines changed

‎README.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -190,6 +190,8 @@ Golang solution for leetcode. For each problem, there is a simple *_test.go to t
190190
#### [231. Power of Two](https://github.com/hitzzc/go-leetcode/tree/master/power_of_two)
191191
#### [232. Implement Queue using Stacks](https://github.com/hitzzc/go-leetcode/tree/master/implement_queue_using_stacks)
192192
#### [234. Palindrome Linked List](https://github.com/hitzzc/go-leetcode/tree/master/palindrome_lined_list)
193+
#### [235. Lowest Common Ancestor of a Binary Search Tree](https://github.com/hitzzc/go-leetcode/tree/master/lowest_common_ancestor_of_a_binary_search_tree)
194+
#### [235. Lowest Common Ancestor of a Binary Tree](https://github.com/hitzzc/go-leetcode/tree/master/lowest_common_ancestor_of_a_binary_tree)
193195

194196

195197

‎lowest_common_ancestor_of_a_binary_search_tree/lowest_common_ancestor_of_a_binary_search_tree.cpp

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
struct TreeNode {
2+
int val;
3+
TreeNode *left;
4+
TreeNode *right;
5+
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
6+
};
7+
8+
class Solution {
9+
public:
10+
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
11+
if (root == NULL || p->val >= root->val && q->val <= root->val || p->val <= root->val && q->val >= root->val)
12+
return root;
13+
if (p->val <= root->val)
14+
return lowestCommonAncestor(root->left, p, q);
15+
return lowestCommonAncestor(root->right, p, q);
16+
}
17+
};

‎lowest_common_ancestor_of_a_binary_tree/lowest_common_ancestor_of_a_binary_tree.cpp

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
#include <vector>
2+
using namespace std;
3+
4+
struct TreeNode {
5+
int val;
6+
TreeNode *left;
7+
TreeNode *right;
8+
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
9+
};
10+
11+
class Solution {
12+
public:
13+
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
14+
vector<TreeNode*> path_p = {root};
15+
this->searchNode(root, p, path_p);
16+
vector<TreeNode*> path_q = {root};
17+
this->searchNode(root, q, path_q);
18+
int idx = path_p.size()<path_q.size() ? path_p.size()-1 : path_q.size()-1;
19+
for (;idx >= 0; --idx) {
20+
if (path_p[idx] == path_q[idx]) return path_p[idx];
21+
}
22+
return NULL;
23+
}
24+
25+
bool searchNode(TreeNode* root, TreeNode* target, vector<TreeNode*>& path) {
26+
if (root == target) {
27+
return true;
28+
}
29+
if (root->left == NULL && root->right == NULL) {
30+
return false;
31+
}
32+
if (root->left != NULL){
33+
path.push_back(root->left);
34+
if (searchNode(root->left, target, path)){
35+
return true;
36+
}
37+
path.pop_back();
38+
}
39+
if (root->right != NULL){
40+
path.push_back(root->right);
41+
if (searchNode(root->right, target, path)){
42+
return true;
43+
}
44+
path.pop_back();
45+
}
46+
return false;
47+
}
48+
};

0 commit comments

Comments
 (0)
0