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.
1#include <iostream>
2#include <queue>
3#include <limits.h>
4using namespace std;
5
6// Definition for a binary tree node.
7struct TreeNode {
8 int val;
9 TreeNode *left;
10 TreeNode *right;
11 TreeNode() : val(0), left(nullptr), right(nullptr) {}
12 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
13 TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
14};
15
16int maxLevelSum(TreeNode* root) {
17 if (!root) return 0;
18 queue<TreeNode*> q;
19 q.push(root);
20 int maxSum = INT_MIN, level = 0, maxLevel = 0;
21 while (!q.empty()) {
22 int levelSize = q.size();
23 int levelSum = 0;
24 level++;
25 for (int i = 0; i < levelSize; i++) {
26 TreeNode* node = q.front();
27 q.pop();
28 levelSum += node->val;
29 if (node->left) q.push(node->left);
30 if (node->right) q.push(node->right);
31 }
32 if (levelSum > maxSum) {
33 maxSum = levelSum;
34 maxLevel = level;
35 }
36 }
37 return maxLevel;
38}
39
40int main() {
41 // Example Usage
42 TreeNode* root = new TreeNode(1);
43 root->left = new TreeNode(7);
44 root->right = new TreeNode(0);
45 root->left->left = new TreeNode(7);
46 root->left->right = new TreeNode(-8);
47 cout << "Max Level Sum: " << maxLevelSum(root) << endl;
48 return 0;
49}
50The C++ solution similarly uses a queue to facilitate level-order traversal. By pushing children of each node onto the queue as we visit them, we ensure that the tree is processed level by level. The crucial aspect is keeping track of the current level and its sum, and updating the maximum criteria as levels are processed.
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.