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.
1#include <stdio.h>
2#include <stdlib.h>
3
4typedef struct TreeNode {
5 int val;
6 struct TreeNode* left;
7 struct TreeNode* right;
8} TreeNode;
9
10int deepestLeavesSum(TreeNode* root) {
11 if (!root) return 0;
12
13 TreeNode** queue = malloc(10000 * sizeof(TreeNode*));
14 int head = 0, tail = 0;
15 queue[tail++] = root;
16 int sum = 0;
17
18 while (head < tail) {
19 int level_size = tail - head;
20 sum = 0;
21 for (int i = 0; i < level_size; i++) {
22 TreeNode* node = queue[head++];
23 sum += node->val;
24 if (node->left) queue[tail++] = node->left;
25 if (node->right) queue[tail++] = node->right;
26 }
27 }
28
29 free(queue);
30 return sum;
31}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.
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.
1using System;
2
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
private int maxDepth = 0;
private int sum = 0;
private void DFS(TreeNode node, int depth) {
if (node == null) 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);
}
public int DeepestLeavesSum(TreeNode root) {
DFS(root, 0);
return sum;
}
}C# solution runs a similar DFS, tracking max depth and adjusting sums in a depth-first traversal manner, using recursion.