Mid/Senior
Lowest Common Ancestor of a Binary Tree III
Given two nodes p and q in a binary tree, return their lowest common ancestor (LCA).
Each node in the tree has an additional parent pointer that points to its parent node. The root node's parent is null.
The lowest common ancestor of two nodes p and q is the lowest node in the tree that has both p and q as descendants, where a node can be a descendant of itself.
For this problem entry, the tree is provided as root in level-order form, and the unique values p and q identify the two target nodes. Return the value of their lowest common ancestor.
Example 1
3
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4Input
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1Output
3Nodes 5 and 1 have node 3 as their lowest common ancestor.
Example 2
3
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4Input
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4Output
5Node 5 is an ancestor of node 4, so their lowest common ancestor is 5.
Constraints
- 2 <= number of nodes <= 10^5
- -10^9 <= Node.val <= 10^9
- All Node.val are unique.
- p != q
- p and q exist in the tree.