Maximum Level Sum of a Binary Tree

1package pkg5leetcode.official75;2 3/*4 * Maximum Level Sum of a Binary Tree | LC 11615 * APPROACH: BFS sum each level; track max level.6 * COMPLEXITY: Time O(n), Space O(n)7 */8import java.util.*;9 10public class official75_LC1161MaximumLevelSumOfBinaryTree {11    /** Same shape as pkg5leetcode/common/TreeNode.java (nested for single-file runs). */12 13    static class TreeNode {14        int val;15        TreeNode left, right;16        TreeNode(int val) { this.val = val; }17    }18 19    static int maxLevelSum(TreeNode root) {20        Deque<TreeNode> q = new ArrayDeque<>();21        q.add(root);22        int level = 1, bestLevel = 1, bestSum = Integer.MIN_VALUE;23        while (!q.isEmpty()) {24            int size = q.size(), sum = 0;25            for (int i = 0; i < size; i++) {26                TreeNode node = q.poll();27                sum += node.val;28                if (node.left != null) q.add(node.left);29                if (node.right != null) q.add(node.right);30            }31            if (sum > bestSum) { bestSum = sum; bestLevel = level; }32            level++;33        }34        return bestLevel;35    }36 37    public static void main(String[] args) {38        TreeNode root = new TreeNode(1);39        root.left = new TreeNode(7); root.right = new TreeNode(0);40        root.left.left = new TreeNode(7); root.left.right = new TreeNode(-8);41        check(maxLevelSum(root) == 2, "case1");42        TreeNode r2 = new TreeNode(989);43        r2.right = new TreeNode(10250); r2.right.right = new TreeNode(98693);44        r2.right.right.left = new TreeNode(-89388); r2.right.right.right = new TreeNode(69081);45        r2.right.right.right.left = new TreeNode(12131);46        check(maxLevelSum(r2) == 3, "case2");47        System.out.println("all tests passed");48    }49 50    static void check(boolean cond, String name) {51        if (!cond) throw new AssertionError("FAILED: " + name);52        System.out.println("  PASS " + name);53    }54}