Lowest Common Ancestor of a Binary Tree

Given the root of a binary tree and two values `p` and `q` that both exist in it, return the value of their lowest common ancestor (the deepest node that has both as descendants, where a node can be a descendant of itself).

Examples

in: root = [3,5,1,6,2,0,8], p = 5, q = 1

out: 3

they split at the root

in: root = [3,5,1,6,2,0,8], p = 5, q = 4

out: 5

(with 4 under 5) 5 is an ancestor of 4

Constraints

2 <= number of nodes <= 10^5
all values are unique
p and q exist

Hints

target: O(n) time⌘↩ run · ⇧⌘↩ submit