noodleProblems/
Lowest Common Ancestor of a Binary Tree
#136

Lowest Common Ancestor of a Binary Tree

AlgorithmmediumTreeDepth First SearchBinary Tree

Given the root of a binary tree and two values p and q present in it, return the value of their **lowest common ancestor** — the deepest node that has both p and q somewhere in its subtree.

A node is allowed to be a descendant of itself, so if p is an ancestor of q, then p is the answer. All node values are unique.

The tree is given as a level-order array where null marks a missing child. (LeetCode returns the ancestor *node*; here we return its value, since values are unique.)

Example cases

  • split
    in root = [3,5,1,6,2,0,8,null,null,7,4]657243018p = 5q = 1
    out 3
    5 and 1 are in different subtrees of the root, so the root 3 is their LCA.
  • ancestor of itself
    in root = [3,5,1,6,2,0,8,null,null,7,4]657243018p = 5q = 4
    out 5
    4 lies in 5's subtree, so 5 is its own answer.
  • two nodes
    in root = [1,2]21p = 1q = 2
    out 1

Constraints

  • The number of nodes in the tree is in the range [2, 10^5].
  • -10^9 <= Node.val <= 10^9
  • All Node.val are unique. p != q, and both p and q exist in the tree.
Saved
root =
[3,5,1,6,2,0,8,null,null,7,4]
p =
5
q =
1