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

﹏ヽ暗。殇╰゛Y 2022-10-10 01:27 21阅读 0赞

## Topic ##

*  Tree
 *  Breadth-First Search

## Description ##

[https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/][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:**

![66387ca3c7fe73a5d0b4efaffb74e973.png][]

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));
        	
        }
    }

[https_leetcode.com_problems_maximum-level-sum-of-a-binary-tree]: https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/
[66387ca3c7fe73a5d0b4efaffb74e973.png]: /images/20221005/f917ca95963e4a5088716c54b1a258d9.png