Use DFS with 2 additional return value leaves_sum and depth. For each node, if it's left depth is the same as right depth, return the sum of 2 value. Else, return the leaves_sum and depth of the deepest children.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def deepestLeavesSum(self, root: TreeNode) -> int:
return self._dfs(root, 0)[0]
def _dfs(self, node, depth):
if node.left and node.right:
l = self._dfs(node.left, depth + 1)
r = self._dfs(node.right, depth + 1)
if l[1] == r[1]:
return l[0] + r[0], l[1]
elif l[1] > r[1]:
return l
else:
return r
elif node.left is not None:
return self._dfs(node.left, depth + 1)
elif node.right is not None:
return self._dfs(node.right, depth + 1)
else:
# This is a leaf node
return node.val, depth