Lowest Common Ancestor

The lowest common ancestor (LCA) of two nodes p and q is the deepest node that has both p and q as descendants. A node counts as its own descendant, so if p is an ancestor of q, the LCA is p.

Given the root of a binary tree and two values p and q that both appear in the tree, return the value of their lowest common ancestor. All node values are distinct.

Examples

        3
       / \
      5   1
     / \ / \
    6  2 0  8
      / \
     7   4

Input:  root = [3, 5, 1, 6, 2, 0, 8, None, None, 7, 4], p = 5, q = 1
Output: 3

Input:  root = [3, 5, 1, 6, 2, 0, 8, None, None, 7, 4], p = 5, q = 4
Output: 5
Explanation: 5 is an ancestor of 4, so it is its own LCA with 4.

  1
 /
2

Input:  root = [1, 2], p = 1, q = 2
Output: 1

Constraints

• 2 <= number of nodes <= 1000
• All values are distinct, and p != q both exist in the tree.

Goals

• Return information upwards from recursive calls and combine it at each node
• Reason about the three cases: both targets on the left, both on the right, or split
• Distinguish 'not found' (None) from a found value of 0