1161.md

1161. Maximum Level Sum of a Binary Tree

Level:

Topic:

Similar Problem:

• 102. Binary Tree Level Order Traversal

Question

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.

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.

Intuition

Recursive:

• save every level's sum to list and then compare

Iterative:

• bfs with queue and compare each level sum

Code

Time: O(n)
Space: O(n)

Recursive

List<Integer> ans = new ArrayList<>();
public int maxLevelSum(TreeNode root) {
    helper(root, 0);
    int maxLevel = 0;
    for (int i = 1; i < ans.size(); i++) {
        if (ans.get(i) > ans.get(maxLevel))
            maxLevel = i;
    }
    return maxLevel+1;
}

private void helper(TreeNode root, int level) {
    if (root == null)
        return;
    if (level == ans.size())
        ans.add(0);

    ans.set(level, ans.get(level)+root.val);
    helper(root.left, level+1);
    helper(root.right, level+1);
}

Iterative

public int maxLevelSum(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    Queue<TreeNode> q = new LinkedList<>();
    if (root != null)
        q.add(root);

    int maxSum = Integer.MIN_VALUE;
    int maxLevel = -1;
    int level = 0;
    while (!q.isEmpty()) {
        int n = q.size();
        int sum = 0;
        while (n-- > 0) {
            root = q.poll();
            sum += root.val;
            if (root.left != null)
                q.add(root.left);
            if (root.right != null)
                q.add(root.right);
        }
        level++;
        if (sum > maxSum) {
            maxLevel = level;
            maxSum = sum;
        }
    }
    return maxLevel;
}