The deepest leaves of a tree are the leaves that are farthest from the root. Return the value of the root of the smallest subtree that contains every deepest leaf (this node is the lowest common ancestor of the deepest leaves). If only one leaf is deepest, the answer is that leaf's own value.
Examples
1
/ \
2 3
/ \
4 5
/ \
7 8
Input: root = build_tree([1, 2, 3, 4, 5, None, None, 7, 8])
Output: 4
Explanation: the deepest leaves are 7 and 8, and node 4 is the lowest node above both.
Input: root = build_tree([1, 2, 3, 4, 5, None, 6, None, None, 7, 8, 9])
Output: 1
Explanation: the deepest leaves 7, 8 and 9 sit on both sides of the root.
Constraints
1 <= number of nodes <= 1000- All values are distinct
Goals
- Return a pair (height, node) from a single post-order pass
- Decide the answer at the node where two equal heights meet