Lowest Common Ancestor

Given the root of a binary tree and two nodes p and q that exist in the tree, find their lowest common ancestor (LCA).

The LCA of two nodes p and q is defined as the lowest (i.e. deepest) node in the tree that has both p and q as descendants (where a node is allowed to be a descendant of itself).

Example 1

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

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

Output: 3.

Example 2

Same tree, p = 5, q = 4 → Output: 5 — node 5 is an ancestor of 4 (through 2), and by definition a node can be its own ancestor, so the lowest node satisfying "ancestor of both" is 5 itself.

Example 3

p = 6, q = 4 → Output: 5.

Constraints

• The number of nodes is in the range [2, 10^5].
• All node values are unique.
• p != q and both p and q are guaranteed to exist in the tree.