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.
1import java.util.LinkedList;
2import java.util.Queue;
3
4class TreeNode {
5 int val;
6 TreeNode left;
7 TreeNode right;
8 TreeNode(int x) { val = x; }
9}
10
11public class Solution {
12 public int deepestLeavesSum(TreeNode root) {
13 if (root == null) return 0;
14
15 Queue<TreeNode> queue = new LinkedList<>();
16 queue.offer(root);
17 int sum = 0;
18
19 while (!queue.isEmpty()) {
20 int size = queue.size();
21 sum = 0;
22 for (int i = 0; i < size; i++) {
23 TreeNode node = queue.poll();
24 sum += node.val;
25 if (node.left != null) queue.offer(node.left);
26 if (node.right != null) queue.offer(node.right);
27 }
28 }
29
30 return sum;
31 }
32}The Java solution follows the BFS method to traverse each tree level completely while summing the node values. The resultant sum post loop execution is the deepest leaves' sum.
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 <iostream>
2#include <algorithm>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int maxDepth = 0;
int sum = 0;
void dfs(TreeNode* node, int depth) {
if (!node) return;
if (depth > maxDepth) {
maxDepth = depth;
sum = node->val;
} else if (depth == maxDepth) {
sum += node->val;
}
dfs(node->left, depth + 1);
dfs(node->right, depth + 1);
}
int deepestLeavesSum(TreeNode* root) {
dfs(root, 0);
return sum;
}
};The C++ solution uses DFS to traverse the binary tree. It tracks both the current depth and the maximum encountered depth to update or add to the sum accordingly.