Решить задачу Lowest Common Ancestor (LeetCode 236)?

LeetCode 236. LCA двух узлов в binary tree. DFS recursion: если p и q в разных subtrees — root = LCA. O(n) время, O(h) память.

# Binary tree — общий случай
def lowestCommonAncestor(root, p, q):
    if not root or root == p or root == q:
        return root
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    if left and right:
        return root       # p и q в разных subtrees
    return left or right

# BST (LeetCode 235) — проще, используем BST property
def lowestCommonAncestor(root, p, q):
    while root:
        if p.val < root.val > q.val:
            root = root.left
        elif p.val > root.val < q.val:
            root = root.right
        else:
            return root

Edge case: p — ancestor of q → возвращаем p. Для multiple queries — preprocessing: parent pointers + depth, выравниваем глубины. LCA с RMQ (sparse table) — O(1) per query после O(n log n) preprocessing.