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

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

示例1：

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

示例2：

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

示例3：

输入: root = [1]
输出: [1]

示例4：

输入: root = [1,null,2]
输出: [1,2]
解释:      
           1 
            \
             2     

示例5：

输入: root = []
输出: []

提示：

• 二叉树的节点个数的范围是 [0,104]
• -231 <= Node.val <= 231 - 1

思路

与102. 二叉树的层序遍历思路相同。

public List<Integer> largestValues(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) {
        return res;
    }
    ArrayDeque<TreeNode> deque = new ArrayDeque<TreeNode>();
    deque.offer(root);
    int level = 0;
    List<Integer> row = new ArrayList<>();
    int maxVal = Integer.MIN_VALUE;
    while (!deque.isEmpty()) {
        level = deque.size();
        while (level > 0) {
            root = deque.poll();
            level--;
            maxVal = Math.max(maxVal, root.val);
            if (level == 0) {
                res.add(maxVal);
            }
            if (root.left != null) {
                deque.offer(root.left);
            }
            if (root.right != null) {
                deque.offer(root.right);
            }
        }
        maxVal = Integer.MIN_VALUE;
    }
    return res;
}