Deepest Leaves Sum - Leetcode Solution

The Deepest Leaves Sum problem on LeetCode requires finding the sum of the values of the nodes at the deepest level of a binary tree. In order to solve this problem, we need to perform a depth-first search on the binary tree and keep track of the level of each node. At the deepest level, we can add up the values of the nodes and return the sum.

The problem can be broken down into the following steps:

Step 1: Define a variable to keep track of the deepest level of the binary tree. Set it to 0 initially.

Step 2: Define a variable to keep track of the sum of the values of the deepest nodes. Set it to 0 initially.

Step 3: Start a depth-first search of the binary tree. During this traversal, keep track of the level of each node.

Step 4: At each node, check if its level is greater than the current deepest level. If it is, update the deepest level to the level of the current node.

Step 5: If the level of the current node is equal to the deepest level, add its value to the sum of the deepest nodes.

Step 6: Once the traversal is complete, return the sum of the deepest nodes.

Here is an implementation of the solution in Python:

class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        deepest_level = 0
        deepest_sum = 0
        
        def dfs(node, level):
            nonlocal deepest_level, deepest_sum
            
            if not node:
                return
            
            if level > deepest_level:
                deepest_level = level
                deepest_sum = node.val
                
            elif level == deepest_level:
                deepest_sum += node.val
                
            dfs(node.left, level + 1)
            dfs(node.right, level + 1)
        
        dfs(root, 0)
        return deepest_sum

In the above implementation, we use a nested function dfs to perform the depth-first search. We pass the root node of the binary tree and the current level to the dfs function. At each node, we update the deepest level and the sum of the deepest nodes if needed. We then recur on the left and right child of the current node. Finally, we return the sum of the deepest nodes.

1