In graph theory and computer science, the lowest common ancestor (LCA) of two nodes is the lowest node that has both of them as descendants.
Let’s take an example:
LCA(5, 1) => 3
LCA(5, 4) => 5
LCA(5, 0) => 3
LCA(6, 4) => 5
Approach #1 : Recursive Algorithm
There are three scenarios for nodes w, v:
- There is another node
pis LCA ofwandv -
wis in the right subtree ofv(orvis in the right subtree ofw) -
wis in the left subtree ofv(orvis in the left subtree ofw)
So we can use a recursive algorithm to find the LCA of left subtree and LCA of right subtree.
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == NULL || root == p || root == q) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if(left != NULL && right != NULL)
return root; //scenario #1
if(right != NULL)
return right; //scenario #2
return left; //scenario #3
}
};
Time complexity: O(N)
Approach #2 : Iteractive algorithm with Map and Set
We can a stack to traverse the binary tree and use a map record the parent of each node. With this map we could build a set contains all parents of w, and check the parents of v from bottom to top, return the first common parent.
#include <iostream>
#include <set>
#include <map>
#include <stack>
using namespace std;
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
stack<TreeNode*> stack;
map<TreeNode*, TreeNode*> parents;
set<TreeNode*> parents_set;
stack.push(root);
while(!stack.empty()) {
TreeNode* cur = stack.top();
stack.pop();
if(cur->left) {
stack.push(cur->left);
parents[cur->left] = cur;
}
if(cur->right) {
stack.push(cur->right);
parents[cur->right] = cur;
}
}
TreeNode* t = p;
while(t != root) {
parents_set.insert(t);
t = parents[t];
}
t = q;
while(t != root) {
if(parents_set.count(t)) {
return t;
}
t = parents[t];
}
return root;
}
};
The post Lowest Common Ancestor of a Binary Tree appeared first on Coder's Cat.
Top comments (0)