Using DFS, and in the dfs function, return 2 values p_visited and q_visited. When the first time p_visited equals to q_visited, set the result and return the result.
# 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':
self.result = None
self._helper(root, p, q)
return self.result
def _helper(self, node, p, q):
if node is None:
return False, False
lp, lq = self._helper(node.left, p, q)
rp, rq = self._helper(node.right, p, q)
cp, cq = (p == node), (q == node)
vp, vq = (lp or rp or cp), (lq or rq or cq)
if vp and vq and self.result is None:
self.result = node
return vp, vq