在每个树行中找最大值

一、题目描述：

给定一棵二叉树的根节点 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、思路分析：

深度优先遍历 BFS

需要一个队列，先进先出的按层级遍历二叉树
需要levelSize变量维护当前层剩余大小。每当levelSize==0时，说明某层遍历结束，准备进入下一层。
空节点不能加入队列，否则会影响计算当前层大小
先加入子节点，再更新levelSize，否则会影响计算下一层大小

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if(root == null) 
            return ans;
        Deque<TreeNode> que = new ArrayDeque<>();
        que.addLast(root);
        while(!que.isEmpty()){
            int sz = que.size();
            int tmp = Integer.MIN_VALUE;
            while(sz-->0){
                TreeNode node = que.pollFirst();
                tmp = Math.max(tmp, node.val);
                if(node.left!=null) que.addLast(node.left);
                if(node.right!=null) que.addLast(node.right);
            }
            ans.add(tmp);
        }
        return ans;
    }

}

广度优先遍历（层序遍历）DFS

定义一个队列 queue 来存放节点
遍历队列，挨个节点从头部取出
记录取出的节点数值 val 中的最大值 max，如果有左右节点再加入队列，供下一次遍历使用
最后队列长度为 0 即遍历结束

class Solution {
    int[] map;
    int maxDepth = 0;
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if(root == null) 
            return ans;
        map = new int[10002];
        Arrays.fill(map, Integer.MIN_VALUE);
        dfs(root, 0);
        for(int i=0;i<=maxDepth;i++)
            ans.add(map[i]);
        return ans;
    }
    public void dfs(TreeNode node, int depth){
        if(node == null) 
            return;
        if(depth > maxDepth)
            maxDepth = depth;
        map[depth] = Math.max(map[depth], node.val);
        dfs(node.left, depth+1);
        dfs(node.right, depth+1);
    }
}

四、总结：

掘友们，解题不易，留下个赞或评论再走吧！谢啦~ 💐

希望对你有帮助，期待您找到心意的工作和满意的offer

期待下次再见~

🌇 点赞 👍 收藏 ⭐留言 📝 一键三连 ~关注Jam，从你我做起