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:
[2, 105]
.-109 <= Node.val <= 109
Node.val
are unique.p != q
p
and q
will exist in the tree.Source
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def lowest_common_ancestor(root, p, q):
"""Recursive bottom-up solution using a hashmap of parent pointers"""
def dfs(node, parent):
if not node:
return
if p in parent and q in parent:
return
if node.left:
parent[node.left] = node
dfs(node.left, parent)
if node.right:
parent[node.right] = node
dfs(node.right, parent)
parent = {root:None}
dfs(root, parent)
ancestors = set()
while p: # find all ancestors of p
ancestors.add(p)
p = parent[p]
while q not in ancestors: # while nothing common
q = parent[q]
return q # 1st one to be also an ancestors of p
def lowest_common_ancestor(root, p, q):
"""Alternative recursive bottom-up solution"""
def dfs(node):
nonlocal lca
if not node:
return False # return None is not acceptable because addition below
left = dfs(node.left)
right = dfs(node.right)
curr = True if node in (p, q) else False
if curr + left + right >= 2: # If any two variables is True
lca = node
return curr or left or right # return the one where we found something
lca = None
dfs(root)
return lca
def lowest_common_ancestor(root, p, q):
"""Another alternative recursive bottom-up solution"""
if not root:
return False # return None is acceptable here
if root in (p, q):
return root
# Option A - a bit faster
left = right = None
if root.left:
left = lowest_common_ancestor(root, p, q)
if root.right:
right = lowest_common_ancestor(root, p, q)
# Option B - a bit slower
# left = lowest_common_ancestor(root, p, q)
# right = lowest_common_ancestor(root, p, q)
if left and right: # if we found something on each side
return root
return left or right # otherwise, return the one where we found something
Solve it both recursively and iteratively.
def lowest_common_ancestor(root, p, q):
"""Iterative version of the first solution (with hashmap of parent pointers)"""
stack = [root]
parent = {root: None}
while not (p in parent and q 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