1.题目

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

示例1：

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

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

提示：
二叉树的节点个数的范围是 [0,10⁴]
-2³¹ <= Node.val <= 2³¹ - 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);
        }
    }
}