LeetCode 1161. Maximum Level Sum of a Binary Tree

原题链接在这里：https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/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 1:

Input: root = [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.

Example 2:

Input: root = [989,null,10250,98693,-89388,null,null,null,-32127]
Output: 2

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• -105 <= Node.val <= 105

题解：

Perforom level order traversal. And accumlate sum of each level.

When there is a new maximum, update the max and result level.

Time Complexity: O(n). n is number of nodes in the tree.

Space: O(n).

AC Java:

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode() {}
 8  *     TreeNode(int val) { this.val = val; }
 9  *     TreeNode(int val, TreeNode left, TreeNode right) {
10  *         this.val = val;
11  *         this.left = left;
12  *         this.right = right;
13  *     }
14  * }
15  */
16 class Solution {
17     public int maxLevelSum(TreeNode root) {
18         if(root == null){
19             return 0;
20         }
21 
22         int max = Integer.MIN_VALUE;
23         int res = 0;
24         int level = 1;
25         LinkedList<TreeNode> que = new LinkedList<>();
26         que.add(root);
27         while(!que.isEmpty()){
28             int size = que.size();
29             int sum = 0;
30             while(size-- > 0){
31                 TreeNode cur = que.poll();
32                 sum += cur.val;
33                 if(cur.left != null){
34                     que.add(cur.left);
35                 }
36 
37                 if(cur.right != null){
38                     que.add(cur.right);
39                 }
40             }
41 
42             if(sum > max){
43                 max = sum;
44                 res = level;
45             }
46 
47             level++;
48         }
49 
50         return res;
51     }
52 }