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）层序遍历
Since we want to find the maximum value of each level in the binary tree,Then it can be searched by layer order traversal,while traversing each layer,使用遍历 curMax to store the maximum value of the current layer,After each layer traversal is over,将 curMax 加入到 res 中即可,遍历结束后返回 res.Refer to the specific traversal details102.二叉树的层序遍历这篇文章.

（2）深度优先遍历 (DFS)
See the comments in the code below for details.

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);
                //Save all nodes in the next layer to 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 The subscripts in represent the number of levels in the binary tree（从 0 开始）,The value corresponding to the subscript represents the maximum value in the layer */	
        if (curHeight == res.size()) {
    
        	/* 如果 curHeight == res.size(),那么则说明 res The current chapter has not been saved curHeight 层 information on the maximum value of,So directly add the current node value to res 中 */
            res.add(root.val);
        } else {
    
        	// Update the maximum value of the current layer
            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);
        }
    }
}