Lowest Common Ancestor of a Binary Tree
medium
binary-tree
depth-first-search
Given the root of a binary tree and two integer values p and q that are guaranteed to exist in the tree, return the value of their lowest common ancestor. A node is the lowest common ancestor when it is the deepest node that has both target values in its subtree (where a node can be a descendant of itself).
Input / output
- Input:
root: TreeNode,p: int,q: int(rootis provided in tests as a LeetCode-style level-order array such as[3,5,1,6,2,0,8,null,null,7,4]) - Output:
int— the value of the lowest common ancestor
Constraints
- 2 <= number of nodes <= 100000
- All node values are unique
pandqare different values that both exist in the tree
Follow-up
Can you solve it with a single DFS that returns the matching node from each subtree and detects the first split point without storing parent pointers?
Examples
Example 1
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Example 2
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Example 3
Input: root = [1,2,3,4,5], p = 4, q = 5
Output: 2
🔒 6 hidden
Running will execute all 9 cases, including 6 hidden ones.