You are given the root of a binary tree whose node values are all distinct, and two values a and b that both occur in the tree.
The lowest common ancestor of two nodes is the deepest node that has both of them as descendants, where a node counts as a descendant of itself.
Return the value of the lowest common ancestor of the nodes holding a and b.
Tree Encoding
Your function receives root as a TreeNode. The node type is provided for you, with val, left, and right fields.
The examples below write the tree as its level-order traversal, where null marks a missing child of a listed node and trailing nulls are omitted. That is only how the input is displayed; the decoding is done for you.
Constraints
The number of nodes in the tree is in the range [2,105].
−109≤Node.val≤109
All Node.val are unique.
a != b
a and b both exist in the tree.
Examples
Example 1
Input
root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]
a = 5
b = 1
root
Output
3
Explanation
5 is in the left subtree of 3 and 1 is the right child of 3, so 3 is their lowest common ancestor.
Example 2
Input
root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]
a = 5
b = 4
root
Output
5
Explanation
4 is a descendant of 5 (through 2), and a node is its own descendant, so the answer is 5.
Example 3
Input
root = [1, 2]
a = 1
b = 2
root
Output
1
Explanation
1 is the root, so it is an ancestor of every node in the tree, including itself.
Loading editor...
Run checks the sample cases; Submit runs every case.
Samples 3
Custom 0
passedwrong answertime limiterrorran, no expected valuenot run