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: 15
Example 2:
Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5] Output: 19
Constraints:
[1, 104].1 <= Node.val <= 100This approach leverages a Breadth-First Search (BFS) traversal method using a queue to explore each level of the binary tree fully before moving on to the next level. By summing values at each level during the traversal, we can determine the sum of the deepest leaves by replacing the sum at every level.
We initialize a queue and push the root node into it. Then, we iterate while the queue is not empty, processing all nodes at the current level and updating the sum. If there are nodes left to explore after processing a level, we reset the sum for the next level.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of nodes in the binary tree.
Space Complexity: O(n), for storing nodes in the queue.
This alternative approach uses Depth-First Search (DFS) to traverse the binary tree and keeps track of the maximum depth and accumulated sum of the node values at that depth.
In this C implementation, we perform a DFS, updating the max depth and sum at that depth. When equal to max depth, accumulate the node values.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(h), where h is the height of the tree due to recursion stack.
| Approach | Complexity |
|---|---|
| Level Order Traversal (BFS) | Time Complexity: O(n), where n is the number of nodes in the binary tree. |
| Depth-First Search (DFS) | Time Complexity: O(n) |
LeetCode 1302. Deepest Leaves Sum (Algorithm Explained) • Nick White • 12,894 views views
Watch 9 more video solutions →Practice Deepest Leaves Sum with our built-in code editor and test cases.
Practice on FleetCode