515. 在每个树行中找最大值

Love The Way You Lie 2023-10-04 09:20 18阅读 0赞

您需要在二叉树的每一行中找到最大的值。

**示例：**

输入: 
    
              1
             / \
            3   2
           / \   \  
          5   3   9 
    
    输出: [1, 3, 9]

package Solution515;
    
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Queue;
    
    class Solution {
    	public List<Integer> largestValues(TreeNode root) {
    		if (root == null) {
    			return Collections.emptyList();
    		}
    		Queue<TreeNode> queue = new LinkedList<TreeNode>();
    		queue.add(root);
    		int count = 1;
    		List<Integer> finalList = new ArrayList<Integer>();
    		while (count != 0) {
    			List<Integer> list = new ArrayList<Integer>();
    			Queue<TreeNode> nextQueue = new LinkedList<TreeNode>();
    			while (!queue.isEmpty()) {
    				TreeNode node = queue.poll();
    				list.add(node.val);
    				count--;
    				if (node.left != null) {
    					nextQueue.add(node.left);
    				}
    				if (node.right != null) {
    					nextQueue.add(node.right);
    				}
    			}
    			Collections.sort(list);
    			finalList.add(list.get(list.size() - 1));
    			count = nextQueue.size();
    			queue = nextQueue;
    		}
    		return finalList;
    	}
    
    	public static void main(String[] args) {
    
    		Solution same = new Solution();
    
    		TreeNode first = new TreeNode(3);
    		first.left = new TreeNode(9);
    		first.right = new TreeNode(20);
    		first.right.left = new TreeNode(15);
    		first.right.right = new TreeNode(7);
    
    		System.out.println(same.largestValues(first));
    	}
    
    }