52. Lowest Common Ancestor of a Binary Tree

Medium · Binary Tree

Given a binary tree and two nodes in that tree, find the lowest common ancestor (LCA) of the two nodes. The lowest common ancestor is the deepest node that is an ancestor of both given nodes. A node can be an ancestor of itself.

The tree is encoded as a level-order array where each element is either a node value (number) or null for missing children. Nodes are identified by their values, which are unique within the tree.

Examples

Example 1
Input: tree = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 1
Output: 3
Explanation: The tree structure is:
       3
      / \
     5   1
    / \ / \
   6  2 0  8
     / \
    7   4
The LCA of nodes 5 and 1 is 3, since 3 is the deepest node that has both 5 and 1 as descendants.
Example 2
Input: tree = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since 5 is an ancestor of 4 and a node can be an ancestor of itself.

Constraints