LeetCode 1302. Deepest Leaves Sum



Given a binary tree, return the sum of values of its deepest leaves.

Example 1:

Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15


  • The number of nodes in the tree is between 1 and 10^4.
  • The value of nodes is between 1 and 100.


First find the max depth of the tree, then find leave nodes at deepest level and sum their values.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        self.max_depth = self.find_max_depth(root)
        self.deepest_sum = 0
        self.get_deepest_sum(root, 1)
        return self.deepest_sum
    def get_deepest_sum(self, root, depth):
        if not root:
        if not root.left and not root.right:        
            if depth == self.max_depth:
                self.deepest_sum += root.val
        self.get_deepest_sum(root.left, depth + 1)
        self.get_deepest_sum(root.right, depth + 1)
    def find_max_depth(self, root):
        if not root:
            return 0
        if not root.left and not root.right:
            return 1
        left = self.find_max_depth(root.left)
        right = self.find_max_depth(root.right)
        return max(left, right) + 1
  • Time Complexity: O(N)
  • Space Complexity: O(N)

Leave a Reply

Your email address will not be published. Required fields are marked *