Given the root of a binary tree and two of its nodes, return the lowest (deepest) node that has both target nodes as descendants. A node is considered a descendant of itself.
All node values in the tree are unique and both target nodes are guaranteed to exist in the tree.
Input
root: the root of a binary tree (level-order array; null marks a missing child)
node1: the first target node
node2: the second target node
Output
The lowest common ancestor node of node1 and node2.
Examples
Example 1
Inputroot = [1, 2, 3], node1 = (node with value 2), node2 = (node with value 3)
Outputthe node with value 1
Example 2
Inputroot = [1, 2, 3, 4, 5, null, 6], node1 = (node with value 4), node2 = (node with value 5)
Outputthe node with value 2
Constraints
All values in the tree are unique.
Both targets are present in the tree.