LeetCode - Medium - 515. Find Largest Value in Each Tree Row

谁借莪１个温暖的怀抱￠ 2022-10-14 01:22 221阅读 0赞

## Topic ##

*  Tree
 *  Depth-first Search
 *  Breadth-first Search

## Description ##

[https://leetcode.com/problems/find-largest-value-in-each-tree-row/][https_leetcode.com_problems_find-largest-value-in-each-tree-row]

Given the `root` of a binary tree, return an array of the largest value in each row of the tree **(0-indexed)**.

![90df2b9d68775c76d1f8cb053b8e3fdc.png][]

**Example 1:**

Input: root = [1,3,2,5,3,null,9]
    Output: [1,3,9]

**Example 2:**

Input: root = [1,2,3]
    Output: [1,3]

**Example 3:**

Input: root = [1]
    Output: [1]

**Example 4:**

Input: root = [1,null,2]
    Output: [1,2]

**Example 5:**

Input: root = []
    Output: []

**Constraints:**

*  The number of nodes in the tree will be in the range  \[ 0 , 1 0 4 \] \[0, 10^4\] \[0,104\].
 *   − 2 31 < = N o d e . v a l < = 2 31 − 1 -2^\{31\} <= Node.val <= 2^\{31\} - 1 −231<=Node.val<=231−1

## Analysis ##

方法一：BFS

方法二：DFS

## Submission ##

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

## Test ##

import static org.junit.Assert.*;
    
    import org.hamcrest.collection.IsEmptyCollection;
    import org.hamcrest.collection.IsIterableContainingInOrder;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree;
    
    public class FindLargestValueInEachTreeRowTest { 
    
    	@Test
    	public void test() { 
    		FindLargestValueInEachTreeRow obj = new FindLargestValueInEachTreeRow();
    
    		assertThat(obj.largestValues(BinaryTree.integers2BinaryTree(1, 3, 2, 5, 3, null, 9)),//
    				IsIterableContainingInOrder.contains(1, 3, 9));
    		assertThat(obj.largestValues(BinaryTree.integers2BinaryTree(1, 2, 3)),//
    				IsIterableContainingInOrder.contains(1, 3));
    		assertThat(obj.largestValues(BinaryTree.integers2BinaryTree(1)),//
    				IsIterableContainingInOrder.contains(1));
    		assertThat(obj.largestValues(BinaryTree.integers2BinaryTree(1, null, 2)),//
    				IsIterableContainingInOrder.contains(1, 2));
    		assertThat(obj.largestValues(null), IsEmptyCollection.empty());
    	}
    	
    	@Test
    	public void test2() { 
    		FindLargestValueInEachTreeRow obj = new FindLargestValueInEachTreeRow();
    		
    		assertThat(obj.largestValues2(BinaryTree.integers2BinaryTree(1, 3, 2, 5, 3, null, 9)),//
    				IsIterableContainingInOrder.contains(1, 3, 9));
    		assertThat(obj.largestValues2(BinaryTree.integers2BinaryTree(1, 2, 3)),//
    				IsIterableContainingInOrder.contains(1, 3));
    		assertThat(obj.largestValues2(BinaryTree.integers2BinaryTree(1)),//
    				IsIterableContainingInOrder.contains(1));
    		assertThat(obj.largestValues2(BinaryTree.integers2BinaryTree(1, null, 2)),//
    				IsIterableContainingInOrder.contains(1, 2));
    		assertThat(obj.largestValues2(null), IsEmptyCollection.empty());
    	}
    }

[https_leetcode.com_problems_find-largest-value-in-each-tree-row]: https://leetcode.com/problems/find-largest-value-in-each-tree-row/
[90df2b9d68775c76d1f8cb053b8e3fdc.png]: /images/20221014/e69f9933bc67457586f459bcc0638a35.png