Solved! Leetcode 1161. Maximum Level Sum of a Binary Tree

source: https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/description/

Maximum Level Sum of a Binary Tree

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

Solution

/**
 * 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) {
        return bfs(root);
    }

    private int bfs(TreeNode root){
        Map<Integer, Integer> map = new HashMap<>();
        Queue<TreeNode> next = new LinkedList<>();
        Queue<TreeNode> curr = null;
        next.offer(root);
        int level = 0;
        while(!next.isEmpty()){
            curr = next;
            next = new LinkedList<>();
            int sum =0;
            while(!curr.isEmpty()){
                TreeNode temp = curr.poll();
                sum += temp.val;
                if(temp.left!=null)
                    next.offer(temp.left);
                if(temp.right!=null)
                    next.offer(temp.right);
            }

            map.put(++level, sum);

        }
        int maxLevel = 0;
        int max = Integer.MIN_VALUE;

        System.out.println(map);
        for(Map.Entry<Integer, Integer> entry: map.entrySet()){
            if(entry.getValue() > max){
                max = entry.getValue();
                maxLevel = entry.getKey();
            }
        }

        return maxLevel;
    }
}

/**

* 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) {

return bfs(root);

}

private int bfs(TreeNode root){

Map<Integer, Integer> map = new HashMap<>();

Queue<TreeNode> next = new LinkedList<>();

Queue<TreeNode> curr = null;

next.offer(root);

int level = 0;

while(!next.isEmpty()){

curr = next;

next = new LinkedList<>();

int sum =0;

while(!curr.isEmpty()){

TreeNode temp = curr.poll();

sum += temp.val;

if(temp.left!=null)

next.offer(temp.left);

if(temp.right!=null)

next.offer(temp.right);

}

map.put(++level, sum);

}

int maxLevel = 0;

int max = Integer.MIN_VALUE;

System.out.println(map);

for(Map.Entry<Integer, Integer> entry: map.entrySet()){

if(entry.getValue() > max){

max = entry.getValue();

maxLevel = entry.getKey();

}

return maxLevel;

}

Rate this post

Coddicted