LeetCode - Medium - 1161. Maximum Level Sum of a Binary Tree-蒲公英云

LeetCode - Medium - 1161. Maximum Level Sum of a Binary Tree

Topic

Tree
Breadth-First Search

Description

https://leetcode.com/problems/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 , 1 0 4 ] [1, 10^4] [1,104].
− 1 0 5 < = N o d e . v a l < = 1 0 5 -10^5 <= Node.val <= 10^5 −105<=Node.val<=105

Analysis

方法一：BFS

方法二：DFS

Submission

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import com.lun.util.BinaryTree.TreeNode;
public class MaximumLevelSumOfABinaryTree { 
    //方法一：BFS
    public int maxLevelSum(TreeNode root) { 
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int level = 0, minLevel = 0, maxSum = Integer.MIN_VALUE;
        while(!queue.isEmpty()) { 
            level++;
            int sum = 0;
            for(int size = queue.size(); size > 0; size--) { 
                TreeNode node = queue.poll();
                sum += node.val;
                if(node.left != null)
                    queue.offer(node.left);
                if(node.right != null)
                    queue.offer(node.right);
            }
            if(sum > maxSum) { 
                minLevel = level;
                maxSum = sum;
            }
        }
        return minLevel;
    }
    //方法一：DFS
    public int maxLevelSum2(TreeNode root) { 
        List<Integer> tmp = new ArrayList<>();
        int minLevel = 0, maxSum = Integer.MIN_VALUE;
        maxLevelSum2(root, 0, tmp);
        for(int i = 0; i < tmp.size(); i++) { 
            int sum = tmp.get(i);
            if(sum > maxSum) { 
                minLevel = i + 1;
                maxSum = sum;
            }
        }
        return minLevel;
    }
    private void maxLevelSum2(TreeNode node, int level, List<Integer> tmp) { 
        if(node == null) return;
        if(tmp.size() == level) { 
            tmp.add(node.val);
        }else { 
            int sum = tmp.get(level) + node.val;
            tmp.set(level, sum);
        }
        maxLevelSum2(node.left, level + 1, tmp);
        maxLevelSum2(node.right, level + 1, tmp);
    }
}

Test

import static org.junit.Assert.*;
import org.junit.Test;
import com.lun.util.BinaryTree;
import com.lun.util.BinaryTree.TreeNode;
public class MaximumLevelSumOfABinaryTreeTest { 
    @Test
    public void test() { 
        MaximumLevelSumOfABinaryTree mObj = new MaximumLevelSumOfABinaryTree();
        TreeNode root1 = BinaryTree.of(1,7,0,7,-8,null,null);
        assertEquals(2, mObj.maxLevelSum(root1));
        TreeNode root2 = BinaryTree.of(989,null,10250,98693,-89388,null,null,null,-32127);
        assertEquals(2, mObj.maxLevelSum(root2));
        TreeNode root3 = BinaryTree.of(-100,-200,-300,-20,-5,-10,null);
        assertEquals(3, mObj.maxLevelSum(root3));
    }
    @Test
    public void test2() { 
        MaximumLevelSumOfABinaryTree mObj = new MaximumLevelSumOfABinaryTree();
        TreeNode root1 = BinaryTree.of(1,7,0,7,-8,null,null);
        assertEquals(2, mObj.maxLevelSum2(root1));
        TreeNode root2 = BinaryTree.of(989,null,10250,98693,-89388,null,null,null,-32127);
        assertEquals(2, mObj.maxLevelSum2(root2));
        TreeNode root3 = BinaryTree.of(-100,-200,-300,-20,-5,-10,null);
        assertEquals(3, mObj.maxLevelSum2(root3));
    }
}