BinarySearch 0065 Sum of the Deepest Nodes

Problem statement

https://binarysearch.com/problems/Sum-of-the-Deepest-Nodes/

Solution

Equal to leetcode 1302. Deepest Leaves Sum

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, root):
        def dfs1(node):
            if not node: return 0
            return max(dfs1(node.left), dfs1(node.right)) + 1
        
        depth = dfs1(root)
        self.ans = []
        
        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)
            
        dfs2(root, 1)
        return sum(self.ans)