Sum of the Deepest Leaves

Given the root of a binary tree, return the sum of the values on the deepest level. All nodes on the deepest level are leaves. Return 0 for an empty tree.

Examples

        1
       / \
      2   3
     / \   \
    4   5   6
   /         \
  7           8

Input:  root = build_tree([1, 2, 3, 4, 5, None, 6, 7, None, None, None, None, 8])
Output: 15
Explanation: the deepest level holds 7 and 8.

Input:  root = build_tree([3, 9, 20, None, None, 15, 7])
Output: 22

Constraints

• 0 <= number of nodes <= 2000
• -10**4 <= node.val <= 10**4
• Target complexity: O(n) time.

Goals

• Identify the last level of a level-order traversal
• Sum a level while it is being processed
• Handle chains where the deepest level has one node