1161. Maximum Level Sum of a Binary Tree

[songyy5517]

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

Intuition The problem is basicallly to find the layer with the maximum sum of its nodes. A straightforward idea is to travarse the whole tree using BFS. For each layer, we calculate the sum of all its nodes and compare with the global maximum sum.

[songyy5517]

Approach: BFS

1. Exception handling;
2. Define variables:
   • max_layer: records the number of the layer with the maximum node sum;
   • max_sum: records the global maximum layer node sum;
   • cur_layer: the current layer that is travarsing;
3. BFS: （1）For each layer, calculate the sum of all its nodes and compare with the global maximum; （2）Update relative variables;
4. Return max_layer;

Complexity Analysis

• Time complexity: $O(N)$ , travarsing all the nodes in the tree takes $O(N)$ time;
• Space complexity: $O(N)$ , addtionally define a queue used for BFS, which takes up $O(N)$ time.

[songyy5517]

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxLevelSum(TreeNode root) {
        // Intuition: BFS, calculate the sum of each layer
        // 1. Exception handling
        if (root == null)
            return 0;

        // 2. Define variables
        int cur_layer = 1, max_layer = 1, max_sum = root.val;
        Queue<TreeNode> queue = new LinkedList();
        queue.add(root);

        // 3. BFS
        while (!queue.isEmpty()){
            int node_num = queue.size();
            int sum = 0;
            for (int i = 0; i < node_num; i++){
                TreeNode cur = queue.remove();
                sum += cur.val;
                if (cur.left != null) queue.add(cur.left);
                if (cur.right != null) queue.add(cur.right);
            }
            if (sum > max_sum){
                max_sum = sum;
                max_layer = cur_layer;
            }
            cur_layer ++;
        }

        return max_layer;
    }
}

[songyy5517]

2024/6/7