T515、每个数中找最大值

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

示例：

输入:

      1
     / \
    3   2
   / \   \  
  5   3   9 

输出: [1, 3, 9]
通过次数13,314提交次数21,928

解

遇到树相关的题第一反应到递归求解，这个题和树的层次遍历非常相似。使用一个队列记录下一层节点的顺序，然后依次找到每层的最大值即可。遇到这种题需要第一时间在脑袋里反应出解题思路，然后按照模型写代码即可。

    public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null)
            return res;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            int max = Integer.MIN_VALUE;
            for(int i = 0; i < size; i++){
                TreeNode t = queue.poll();
                max = Math.max(max,t.val);
                if(t.left != null)
                    queue.offer(t.left);
                if(t.right != null)
                    queue.offer(t.right);
            }
            res.add(max);
        }
        return res;
    }