Lowest Common Ancestor
mediumTreeHash TableTwo pointers
Given two nodes p and q from a tree, return their lowest common ancestor.
Each node has a reference to its parent node and children nodes. There may be any number of children.
A node counts as a descendant of itself, so if one of p and q is an ancestor of
the other, that ancestor is the answer.
Example 1:
Input: tree = [3, null, 5, 1, null, 6, 2, null], p = 5, q = 1
Output: 3
Example 2:
Input: tree = [3, null, 5, 1, null, 6, 2, null, 0, 8, null, null, 7, 4], p = 4, q = 6
Output: 5
Constraints:
2 <= The number of nodes in the tree <= 10^5-10^9 <= Node.val <= 10^9