Sponsored
Sponsored
This 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.
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.
1from collections import deque
2
3class TreeNode:
4 def __init__(self, val=0, left=None, right=None):
5 self.val = val
6 self.left = left
7 self.right = right
8
9class Solution:
10 def deepestLeavesSum(self, root: TreeNode) -> int:
11 q = deque([root])
12
13 while q:
14 sum_level = 0
15 for _ in range(len(q)):
16 node = q.popleft()
17 sum_level += node.val
18 if node.left:
19 q.append(node.left)
20 if node.right:
21 q.append(node.right)
22
23 return sum_levelThe Python solution uses a deque for efficient pop operations. It updates the sum per level and finally returns the last level's sum, which corresponds to the deepest leaves.
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.
Time Complexity: O(n)
Space Complexity: O(h), where h is the height of the tree due to recursion stack.
1#include
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.