Medium

Lowest Common Ancestor of a Binary Tree

LAB

Given a binary tree encoded level-order with -100000 as null and two node values, return their lowest common ancestor value.

EXAMPLES

Example 1

Input
{
  "root": [
    3,
    5,
    1,
    6,
    2,
    0,
    8,
    -100000,
    -100000,
    7,
    4
  ],
  "p": 5,
  "q": 1
}

Output
3

FUNCTION SHAPE

root: intArrayp: intq: int→int

SOLUTION NOTE

Postorder traversal. The FIRST time l + r + curr == 2 (with res still None) is the LCA. Subsequent ancestors will also have sum == 2 but res is already set.

Reveal reference solution +

pythonREFERENCE

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    res = None

    def dfs(root):  # Returns count of p,q in subtree (0, 1, or 2)
        if not root: return 0
        nonlocal res
        l = dfs(root.left)
        r = dfs(root.right)
        curr = root == p or root == q

        if res is None and l + r + curr == 2:
            res = root

        return l + r + curr

    dfs(root)
    return res

TimeO(n)

SpaceO(h)

Open on LeetCode ↗