Problem statement

https://leetcode.com/problems/deepest-leaves-sum/

Solution

Let us do it in easy way:

  1. First use dfs1 to find the deepest level of binary tree, in fact this is problem 104 Maximum Depth of Binary Tree. Nothing very special here: just check depths of children and choose maximum one. So, it is postorder dfs here.
  2. Next, use dfs2 to collect all nodes which are the deepest. It can be sovled easily if we give parametr d as second to our function: each time when we see node with desired depth, we add it to self.ans.

Complexity

Time complexity is O(n), space is O(h).

Code

class Solution:
    def deepestLeavesSum(self, root):
        def dfs1(node):
            if not node: return 0
            return max(dfs1(node.left), dfs1(node.right)) + 1
        
        def dfs2(node, d):
            if not node: return
            if d == depth: self.ans += node.val
            dfs2(node.left, d+1)
            dfs2(node.right, d+1)
        
        self.ans = 0
        depth = dfs1(root)
        dfs2(root, 1)
        return self.ans