1.题目

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

示例1：

输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]

示例2：
输入: root = [1,2,3]
输出: [1,3]

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-largest-value-in-each-tree-row

2.思路

（1）层序遍历
既然要找出该二叉树中每一层的最大值，那么可以通过层序遍历的方式来进行寻找，在遍历每一层时，使用遍历 curMax 来保存当前层的最大值，在每一层遍历结束后，将 curMax 加入到 res 中即可，遍历结束后返回 res。具体的遍历细节可参考102.二叉树的层序遍历这篇文章。

（2）深度优先遍历 (DFS)
具体细节可看下面代码中的注释。

3.代码实现（Java）

//思路1————层序遍历
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        //queue保存层序遍历过程中每一层的所有节点
        Queue<TreeNode> queue = new LinkedList<>();
        //最开始的第一层只有根节点，故先将根节点加入到队列中
        queue.offer(root);
        // while 循环控制从上向下方向的遍历
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            int curMax = Integer.MIN_VALUE;
            // for 循环控制每一层从左向右的遍历
            for (int i = 0; i < levelSize; i++) {
                TreeNode curNode = queue.poll();
                curMax = Math.max(curMax, curNode.val);
                //将下一层中的所有节点保存到 queue 中
                if (curNode.left != null) {
                    queue.offer(curNode.left);
                }
                if (curNode.right != null) {
                    queue.offer(curNode.right);
                }
            }
            res.add(curMax);
        }
        return res;
    }
}

//思路2————深度优先遍历 (DFS)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // res 保存最终结果
    List<Integer> res = new ArrayList<>();
    
    public List<Integer> largestValues(TreeNode root) {
        if (root == null) {
            return res;
        }
        dfs(root, 0);
        return res;
    }
    
    private void dfs(TreeNode root, int curHeight) {
    	/*
			res 中的下标表示二叉树中的层数（从 0 开始），下标对应的值表示该层中的最大值
		*/	
        if (curHeight == res.size()) {
        	/*
        		如果 curHeight == res.size()，那么则说明 res 还未保存当前第 curHeight 层
        		的最大值信息，所以直接将当前节点值加入到 res 中
			*/
            res.add(root.val);
        } else {
        	// 更新当前层的最大值
            res.set(curHeight, Math.max(res.get(curHeight), root.val));
        }
        // 搜索左子树
        if (root.left != null) {
            dfs(root.left, curHeight + 1);
        }
        // 搜索右子树
        if (root.right != null) {
            dfs(root.right, curHeight + 1);
        }
    }
}