Algorithm
Problem Name: 236. Lowest Common Ancestor of a Binary Tree
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3.
Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 Output: 5 Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
Example 3:
Input: root = [1,2], p = 1, q = 2 Output: 1
Constraints:
- The number of nodes in the tree is in the range
[2, 105]. -109 <= Node.val <= 109- All
Node.valare unique. p != qpandqwill exist in the tree.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int match(struct TreeNode *node, struct TreeNode *n) {
if (!node) return 0;
return (node == n || match(node->left, n) || match(node->right, n)) ? 1 : 0;
}
struct TreeNode *traversal(struct TreeNode *node, struct TreeNode *p, struct TreeNode *q) {
struct TreeNode *lca;
// post order traversal
if (node->left) {
lca = traversal(node->left, p, q);
if (lca) return lca;
}
if (node->right) {
lca = traversal(node->right, p, q);
if (lca) return lca;
}
if (node == p && (match(node->left, q) || match(node->right, q))) return node;
if (match(node->left, p) && match(node->right, q)) return node;
return NULL;
}
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
struct TreeNode *node;
node = traversal(root, p, q);
if (!node) node = traversal(root, q, p);
return node;
}
Input
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output
3
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || root == p || root == q) return root;
bool foundP = found(root->left, p);
bool foundQ = found(root->right, q);
if (foundP && foundQ || !foundP && !foundQ) return root;
if (foundP) return lowestCommonAncestor(root->left, p, q);
return lowestCommonAncestor(root->right, p, q);
}
bool found(TreeNode* root, TreeNode* target) {
if (!root) return false;
if (root == target) return true;
return found(root->left, target) || found(root->right, target);
}
};
Input
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output
3
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root;
}
TreeNode leftRoot = lowestCommonAncestor(root.left, p, q);
TreeNode rightRoot = lowestCommonAncestor(root.right, p, q);
if (leftRoot != null && rightRoot != null) {
return root;
}
return leftRoot != null ? leftRoot : rightRoot;
}
}
Input
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output
5
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const lowestCommonAncestor = function(root, p, q) {
const arr = []
traverse(root, [], arr)
let pii
let qii
// in same path
for(let i = 0; i < arr.length; i++) {
let pi = arr[i].indexOf(p.val)
let qi = arr[i].indexOf(q.val)
if(pi !== -1) pii = [i, pi]
if(qi !== -1) qii = [i, qi]
if(pi !== -1 && qi !== -1) {
return new TreeNode( pi <= qi ? p.val : q.val )
}
}
const len = Math.min(arr[pii[0]].length, arr[qii[0]].length)
const pp = arr[pii[0]]
const qp = arr[qii[0]]
for(let i = 0; i < len; i++) {
if(pp[i] !== qp[i]) return new TreeNode(pp[i - 1])
}
};
function traverse(node, path = [], arr) {
if(node == null) return
path.push(node.val)
if(node.left === null && node.right === null) {
arr.push(path.slice(0))
return
}
traverse(node.left, path.slice(0), arr)
traverse(node.right, path.slice(0), arr>
}
Input
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output
5
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def lowestCommonAncestor(
self, root: "TreeNode", p: "TreeNode", q: "TreeNode"
) -> "TreeNode":
parent, stack = {root: None}, [root]
while p not in parent or q not in parent:
node = stack.pop()
if node.left:
parent[node.left] = node
stack.append(node.left)
if node.right:
parent[node.right] = node
stack.append(node.right)
ancestors = set()
while p:
ancestors.add(p)
p = parent[p]
while q not in ancestors:
q = parent[q]
return q
Input
root = [1,2], p = 1, q = 2
Output
1
#6 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0236_LowestCommonAncestorOfABinaryTree
{
private TreeNode result;
public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
{
Find(root, p, q);
return result;
}
public bool Find(TreeNode root, TreeNode p, TreeNode q)
{
if (root == null) return false;
var left = Find(root.left, p, q) ? 1 : 0;
var right = Find(root.right, p, q) ? 1 : 0;
var self = (root == p || root == q) ? 1 : 0;
if (left + right + self >= 2) result = root;
return left + right + self > 0;
}
}
}
Input
root = [1,2], p = 1, q = 2
Output
1