LC 1644 [M] Lowest Common Ancestor of a Binary Tree II - ALawliet/algorithms GitHub Wiki
constraint: p and q do not always exist
you could just check p and q exist first (1st pass), then call the regular LCA (2nd pass), but how can we do it in just 1 pass first time?
trick is to also store the count of p or q so return [root, count of p or q so far] while doing the regular LCA postorder
if it is 2, both p and q are found. if less than 2, one or both were missing.
# 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':
def postorder(x, p, q):
if not x:
return [None, 0]
Lx, Lcount = postorder(x.left, p, q)
Rx, Rcount = postorder(x.right, p, q)
if x == p or x == q:
return [x, Lcount + Rcount + 1]
if Lx and Rx:
return [x, 2]
if Lx:
return Lx, Lcount
else:
return Rx, Rcount
x, count = postorder(root, p, q)
if count < 2:
return None
elif count == 2: # count == 2
return x