# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
found_p = False
found_q = False
queue = [root]
ancestor = {}
while((not found_p or not found_q) and queue):
current = queue.pop()
if not current:
continue
left = current.left
right = current.right
if left:
ancestor[left] = current
if p.val == left.val:
found_p = True
if q.val == left.val:
found_q = True
if right:
ancestor[right] = current
if p.val == right.val:
found_p = True
if q.val == right.val:
found_q = True
queue.append(left)
queue.append(right)
current = p
p_path = [current]
while current != root:
current = ancestor[current]
p_path.append(current)
current = q
q_path = [current]
while current != root:
current = ancestor[current]
q_path.append(current)
lca = root
for i in p_path:
print(i.val, "<-", end=" ")
print()
for i in q_path:
print(i.val, "<-", end=" ")
for i in range(-1, -1 * min(len(q_path), len(p_path)) - 1, -1):
if q_path[i] == p_path[i]:
lca = p_path[i]
elif q_path[i] != p_path[i]:
break
return lca