Leetcode # 1302. Deepest Leaves Sum

Problem

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

Solution

Time Complexity: O(len(tree))
Space Complexity: O(max_depth(tree))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
    leaves_sum, deepest_level = 0, 0
    stack = [(root, 0)]
    while stack:
      curr, level = stack.pop()
      # ... some process about target
      if curr.left is None and curr.right is None and level >= deepest_level:
        if level > deepest_level:
          leaves_sum, deepest_level = 0, level
        leaves_sum += curr.val
          
      for child in [curr.left, curr.right]:
        if child:
          stack.append((child, level + 1))
    return leaves_sum

Last Updated on 2024/04/20 by A1go