LeetCode - Medium - 1302. Deepest Leaves Sum

Love The Way You Lie 2022-10-05 00:40 106阅读 0赞

## Topic ##

*  Tree
 *  Depth-first Search

## Description ##

[https://leetcode.com/problems/deepest-leaves-sum/][https_leetcode.com_problems_deepest-leaves-sum]

Given the root of a binary tree, return the sum of values of its deepest leaves.

**Example 1:**

![bebe94d58255ebf989051b94eb12b330.png][]

Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
    Output: 15

**Example 2:**

Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
    Output: 19

**Constraints:**

*  The number of nodes in the tree is in the range  \[ 1 , 1 0 4 \] \[1, 10^4\] \[1,104\].
 *   1 < = N o d e . v a l < = 100 1 <= Node.val <= 100 1<=Node.val<=100

## Analysis ##

方法一：DFS

方法二：BFS

## Submission ##

import java.util.LinkedList;
    
    import com.lun.util.BinaryTree.TreeNode;
    
    public class DeepestLeavesSum { 
    	
    	//方法一：DFS
        public int deepestLeavesSum(TreeNode root) { 
            int[] sum = { 0}, deepestLevel = { 0};
            dfs(root, 0, sum, deepestLevel);
            return sum[0];
        }
        
        private void dfs(TreeNode node, int currentLevel, int[] sum, int[] deepestLevel) { 
        	if(node == null) return;
        	
        	if(currentLevel >= deepestLevel[0]) { 
        		if(currentLevel > deepestLevel[0]) { 
    	    		deepestLevel[0] = currentLevel;
    	    		sum[0] = 0;
        		}
        		sum[0] += node.val;
        	}
        	
        	dfs(node.left, currentLevel + 1, sum, deepestLevel);
        	dfs(node.right, currentLevel + 1, sum, deepestLevel);
        }
        
        //方法二：BFS
        public int deepestLeavesSum2(TreeNode root) { 
            int sum = 0;
        	LinkedList<TreeNode> queue = new LinkedList<>();
        	queue.offer(root);
            
        	while(!queue.isEmpty()) { 
        		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);
        		}
        	}
            
        	return sum;
        }
        
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree;
    
    public class DeepestLeavesSumTest { 
    
    	@Test
    	public void test() { 
    		DeepestLeavesSum obj = new DeepestLeavesSum();
    
    		assertEquals(15, obj.deepestLeavesSum(BinaryTree.integers2BinaryTree(1,2,3,4,5,null,6,7,null,null,null,null,8)));
    		assertEquals(19, obj.deepestLeavesSum(BinaryTree.integers2BinaryTree(6,7,8,2,7,1,3,9,null,1,4,null,null,null,5)));
    	}
    	
    	@Test
    	public void test2() { 
    		DeepestLeavesSum obj = new DeepestLeavesSum();
    		
    		assertEquals(15, obj.deepestLeavesSum2(BinaryTree.integers2BinaryTree(1,2,3,4,5,null,6,7,null,null,null,null,8)));
    		assertEquals(19, obj.deepestLeavesSum2(BinaryTree.integers2BinaryTree(6,7,8,2,7,1,3,9,null,1,4,null,null,null,5)));
    	}
    }

[https_leetcode.com_problems_deepest-leaves-sum]: https://leetcode.com/problems/deepest-leaves-sum/
[bebe94d58255ebf989051b94eb12b330.png]: /images/20221005/8db8168fe9d14eefa39561c722b53ba4.png