Description
https://leetcode.com/problems/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
Constraints:
- The number of nodes in the tree is between
1and10^4. - The value of nodes is between
1and100.
Explanation
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:
return
if not root.left and not root.right:
if depth == self.max_depth:
self.deepest_sum += root.val
return
self.get_deepest_sum(root.left, depth + 1)
self.get_deepest_sum(root.right, depth + 1)
return
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)