Description
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. The LCA is the lowest node that has both p and q as descendants (where a node can be a descendant of itself).
Examples
Input:
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1Output:
3Explanation:
The LCA of nodes 5 and 1 is 3.
Input:
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4Output:
5Explanation:
The LCA of nodes 5 and 4 is 5 (a node can be descendant of itself).
Input:
root = [10,5,15,2,8,12,20,1,3], p = 1, q = 3Output:
2Explanation:
The LCA of nodes 1 and 3 is 2. Both nodes 1 and 3 are children of node 2, making node 2 their lowest common ancestor. This example demonstrates finding the LCA when both target nodes are leaf nodes with the same direct parent.
Constraints
- •
The number of nodes in the tree is in the range [2, 10⁵] - •
-10⁹ ≤ Node.val ≤ 10⁹ - •
All Node.val are unique. - •
p != q - •
p and q exist in the tree.