Teaching Kids Programming: Videos on Data Structures and Algorithms
Given the root of 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: 15Example 2:
Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 19Constraints:
The number of nodes in the tree is in the range [1, 104].
1 <= Node.val <= 100Hints:
Traverse the tree to find the max depth.
Traverse the tree again to compute the sum required.
Recursive Depth First Search Algorithm to Find the Sum of Deepest Leaves in a Binary Tree
We can perform a Depth First Search Traversal on the Binary Tree and accumulate the sum for each level. We store the sums in a hash map (dictionary) where the keys are levels and values are the corresponding sums.
With DFS, we can do pre-order, in-order, post-order, reverse-in-order etc which do not matter, as long as we pass down the levels in the Recursion. We can also implement the DFS using stack in an iterative manner.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | # 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: Optional[TreeNode]) -> int: if not root: return 0 data = defaultdict(int) def dfs(root, lvl): if not root: return data[lvl] += root.val dfs(root.left, lvl + 1) dfs(root.right, lvl + 1) dfs(root, 0) return data[max(data.keys())] |
# 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: Optional[TreeNode]) -> int: if not root: return 0 data = defaultdict(int) def dfs(root, lvl): if not root: return data[lvl] += root.val dfs(root.left, lvl + 1) dfs(root.right, lvl + 1) dfs(root, 0) return data[max(data.keys())]
Each node in the binary tree is visited once and thus the time complexity is O(N). The space complexity is O(H) where H is the height of the binary tree and in worst cases, the H is equal to N.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - Algorithms to Check If Any Intervals Overlapping (Meeting Rooms)
Next Post: Teaching Kids Programming - Breadth First Search Algorithm to Find the Sum of Deepest Leaves in a Binary Tree