Lowest Common Ancestor of a Binary Tree
Medium · tree dfs
You are given the root of a binary tree and two integers p and q. Return the value of their lowest common ancestor: the deepest node that has both the node holding p and the node holding q somewhere in its subtree. A node counts as part of its own subtree, so if the node holding p sits above the node holding q, the answer is p.
The tree has no ordering at all. All values in it are distinct, so each value picks out exactly one node, and both p and q are guaranteed to be in the tree. They may be equal.
Return the value of the lowest common ancestor as an integer.
Examples
Example 1
Input: root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 1
Output: 3
5 is under the left child of 3 and 1 is under the right child, so 3 is the first node above both.
Example 2
Input: root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 4
Output: 5
4 is a descendant of 5, and a node counts as its own ancestor, so the answer is 5.
Example 3
Input: root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 7, q = 4
Output: 2
Constraints
- The number of nodes is in the range [1, 1000].
- -10^4 <= Node.val <= 10^4, and all values are distinct.
- p and q both appear in the tree. They may be equal.