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.
1using System;
2using System.Collections.Generic;
3
4public class TreeNode {
5 public int val;
6 public TreeNode left;
7 public TreeNode right;
8 public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
9 this.val = val;
10 this.left = left;
11 this.right = right;
12 }
13}
14
15public class Solution {
16 public int DeepestLeavesSum(TreeNode root) {
17 if (root == null) return 0;
18 Queue<TreeNode> queue = new Queue<TreeNode>();
19 queue.Enqueue(root);
20 int sum = 0;
21
22 while (queue.Count > 0) {
23 int size = queue.Count;
24 sum = 0;
25 for (int i = 0; i < size; i++) {
26 TreeNode node = queue.Dequeue();
27 sum += node.val;
28 if (node.left != null) queue.Enqueue(node.left);
29 if (node.right != null) queue.Enqueue(node.right);
30 }
31 }
32
33 return sum;
34 }
35}C# uses a Queue to achieve a level-order traversal, updating the sum at each level, and finally returns the deepest leaves' sum when the queue is exhausted.
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.
1class
The Java solution applies DFS to compute the sum of the deepest leaves using a recursive helper function to track the depth and adjust the sum.