Sponsored
Sponsored
The BFS approach is well-suited for problems involving levels of a binary tree. We will use a queue to process the tree level by level, keeping track of the sum of node values at each level. We will maintain a variable to store the maximum sum encountered and the level corresponding to this maximum sum. By processing level by level, we ensure that when we find a new maximum, it is the smallest level with that sum.
Time Complexity: O(n), where n is the number of nodes in the tree, because each node is enqueued and dequeued exactly once.
Space Complexity: O(m), where m is the maximum number of nodes at any level in the tree, due to the queue holding nodes of a single level.
1using System;
2using System.Collections.Generic;
3
4// Definition for a binary tree node.
5class TreeNode {
6 public int val;
7 public TreeNode left;
8 public TreeNode right;
9 public TreeNode(int x) { val = x; }
10}
11
12public class Solution {
13 public int MaxLevelSum(TreeNode root) {
14 if (root == null) return 0;
15 Queue<TreeNode> queue = new Queue<TreeNode>();
16 queue.Enqueue(root);
17 int maxSum = int.MinValue;
18 int level = 0;
19 int maxLevel = 0;
20
21 while (queue.Count > 0) {
22 int levelSize = queue.Count;
23 int levelSum = 0;
24 level++;
25 for (int i = 0; i < levelSize; i++) {
26 TreeNode node = queue.Dequeue();
27 levelSum += node.val;
28 if (node.left != null) queue.Enqueue(node.left);
29 if (node.right != null) queue.Enqueue(node.right);
30 }
31 if (levelSum > maxSum) {
32 maxSum = levelSum;
33 maxLevel = level;
34 }
35 }
36 return maxLevel;
37 }
38
39 public static void Main(string[] args) {
40 TreeNode root = new TreeNode(1);
41 root.left = new TreeNode(7);
42 root.right = new TreeNode(0);
43 root.left.left = new TreeNode(7);
44 root.left.right = new TreeNode(-8);
45 Solution solution = new Solution();
46 Console.WriteLine("Max Level Sum: " + solution.MaxLevelSum(root));
47 }
48}
49The C# solution employs a Queue to perform BFS traversal of the tree. The solution tracks the sum at each level and determines the maximum, updating the level variable whenever a new maximum is found.
This approach involves using a DFS traversal to explore the tree. We pass the current depth as a parameter to each recursive call and maintain an array or dictionary to track the sum of values at each level. After the traversal, we determine which level has the highest sum. DFS allows us to explore the tree deeply, and since each call carries a depth count, we can easily track levels.
Time Complexity: O(n)
Space Complexity: O(d), where d is the maximum depth of the tree (related to recursion stack depth and level count in the dictionary).
1from collections import defaultdict
2
3# Definition for a binary tree node.
4class TreeNode
The Python solution uses DFS by recursively traversing the tree and tracking the sum of node values at each level using a dictionary. After completing the traversal, it identifies the level with the maximum sum.