LeetCode 1161. Maximum Level Sum of a Binary Tree (Medium)

Description: Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on.

Return the smallest level X such that the sum of all the values of nodes at level X is maximal. Example:

Input: [1,7,0,7,-8,null,null] Output: 2 Explanation: Level 1 sum = 1. Level 2 sum = 7 + 0 = 7. Level 3 sum = 7 + -8 = -1. So we return the level with the maximum sum which is level 2.

Note:

1.The number of nodes in the given tree is between 1 and 10^4. 2.-10^5 <= node.val <= 10^5

---

Analysis: It is easy to think about using BFS. However, the difficult point of this problem is how to figure out the number of current level that we are visiting since there is no member variable of the Node Class representing the current level. The solution is that we can put all nodes of one level into a queue before visiting this level. We use a loop to visit the tree. In each execution of the loop, we invoke the method queue.size() to get the number of nodes in this level, and then use another loop to traverse these nodes as well as add the nodes of the next level to the queue.

---

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int maxLevelSum(TreeNode root) { if(root == null) { return 0; }else{ int maxSum = Integer.MIN_VALUE; int maxLevel = 0; int curLevel = 0; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while(queue.peek() != null) { curLevel++; int levelSum = 0; int levelNodeSize = queue.size(); for(int i = 0; i < levelNodeSize; i++) { TreeNode node = queue.poll(); levelSum += node.val; if(node.left != null) { queue.offer(node.left); } if(node.right != null) { queue.offer(node.right); } } if(levelSum > maxSum) { maxSum = levelSum; maxLevel = curLevel; } } return maxLevel; } } }