LeetCode二叉树每层的最大值

剑指 Offer II 044. 二叉树每层的最大值

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

输入: root = [1,3,2,5,3,null,9] 输出: [1,3,9] 解释: 1 / 3 2 / \ \ 5 3 9

来源：力扣（LeetCode）

采用广度优先搜索（层序遍历）解决问题。

层序遍历实现过程类似于队列，遍历完当前节点后将其左孩子以及右孩子依次加入队列，这样就能保证出队列的时候对于每一层都是从左往右；而且每次遍历到一个节点的时候，都这样做，直至遍历到最后一层。

新建队列，与层序遍历不同之处在于，需要每次在队列中的应该是一层二叉树的节点，这样就能找到每一层的最大值。

也就是说在while循环里面，当一个节点出队列，但同时它的左孩子和右孩子节点加入队列，这样就能保证当当前层节点全部出队列之和，剩下的就是下一层的全部结点。

至于什么时候找最大值，应该是在每次遍历每一层节点之前就定义一个max，且max随着每一层的遍历不断地进行更新。

至于每一层遍历结束的条件：当本层的元素全部出队列之后，要更新len，记录新一层进入队列的个数。

class Solution {
    public List largestValues(TreeNode root) {
        List ans = new ArrayList();
        if(root==null){
            return new ArrayList();
        }
        Queue queue= new ArrayDeque();
        queue.offer(root);
        while(!queue.isEmpty()){
        int len=queue.size();
        int max=Integer.MIN_VALUE;
        while(len>0){
            TreeNode t = queue.poll();
            len--;
            max=Math.max(t.val,max);
            if(t.left!=null){
                queue.offer(t.left);
            }
            if(t.right!=null){
                queue.offer(t.right);
            }
        }
        ans.add(max);
        }
        return ans;
    }
}

注意，有root等于null的情况，此时就直接返回空的集合即可，但是这种情况应该考虑到。