Description
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes. The LCA is the deepest node having both as descendants.
Examples
Input:
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1Output:
3Explanation:
LCA of 5 and 1 is 3.
Input:
root = [1,2,3,4,5], p = 4, q = 5Output:
2Explanation:
LCA of nodes 4 and 5 is node 2. Both nodes 4 and 5 are children of node 2, making node 2 their lowest common ancestor.
Input:
root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8Output:
6Explanation:
LCA of nodes 2 and 8 is the root node 6. Node 2 is in the left subtree and node 8 is in the right subtree of the root, so their lowest common ancestor is the root itself.
Constraints
- •
2 ≤ number of nodes ≤ 10⁵