The root has depth 0, its children depth 1, and so on. Given the root of a binary tree,
return the sum of the values of all nodes at an even depth (0, 2, 4, ...).
Examples
1 depth 0
/ \
2 3 depth 1
/ \ \
4 5 6 depth 2
Input: root = build_tree([1, 2, 3, 4, 5, None, 6])
Output: 16
Explanation: 1 + 4 + 5 + 6 = 16.
Input: root = build_tree([3, 9, 20, None, None, 15, 7])
Output: 25
Constraints
0 <= number of nodes <= 2000-10**4 <= node.val <= 10**4- Target complexity: O(n) time.
Goals
- Carry the depth of each node through the traversal
- Filter nodes by the parity of their depth
- Handle negative values and chains