714121. Max Level Sum in Binary Tree
Easy
Max Level Sum in Binary Tree
Slug: max-level-sum-in-binary-tree--170647
Difficulty: Easy
Topic Tags: Binary Search Tree, Binary Search, Tree
Company Tags: Amazon
Summary
Given a binary tree, find the maximum sum of all nodes at any level.
The key concept involved is traversing and manipulating a binary tree to calculate the sum of its nodes at each level.
Detailed Explanation
To solve this problem, we can use a depth-first search (DFS) approach. We will start by initializing an empty list max_sum to store the maximum sum at each level. Then, we will perform DFS traversal on the given binary tree.
Here's the step-by-step breakdown of the solution:
- Initialize an empty list
max_sum. - Perform DFS traversal on the given binary tree.
- At each level, calculate the sum of all nodes and store it in the
max_sumlist. - Return the maximum sum from the
max_sumlist.
Here's a simple example to illustrate this:
1
/ \
2 3
/ \ \
4 5 6
The maximum sum at each level is: [1], [7], [8]. So, the final answer will be 8.
Time complexity analysis:
- The time complexity of DFS traversal on a binary tree is O(n), where n is the number of nodes in the tree.
- Since we are performing this traversal once and calculating the sum at each level, the overall time complexity is also O(n).
Space complexity analysis:
- The space complexity depends on the maximum depth of the binary tree. In the worst-case scenario, it can be O(logn), where n is the number of nodes in the tree.
Optimized Solutions
Java
class Solution {
public int maxLevelSum(TreeNode root) {
if (root == null)
return 0;
List<Integer> max_sum = new ArrayList<>();
int max = Integer.MIN_VALUE;
dfs(root, 1, max_sum);
for (int i : max_sum) {
if (i > max)
max = i;
}
return max;
}
private void dfs(TreeNode node, int level, List<Integer> max_sum) {
if (node == null)
return;
if (max_sum.size() < level) {
max_sum.add(0);
}
max_sum.set(level - 1, max_sum.get(level - 1) + node.val);
dfs(node.left, level + 1, max_sum);
dfs(node.right, level + 1, max_sum);
}
}