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

1 问题

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

示例1

示例1

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

示例2

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

提示

• 二叉树的节点个数的范围是 [1,$10^4$]
• $-2^{31}$<= Node.val <= $2^{31}$ - 1

2 解题思路

本题类似于【LeetCode】199.二叉树的右视图，分层遍历，记录每层的值，然后当每层遍历完时，统计最大值，记录该层的最大值即可。

另外，对于DFS算法，记录下层数，记录每层的最大值即可得解。

3 代码

/**
 * 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 {
    //BFS
    public List<Integer> largestValues2(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        TreeNode tmp;
        q.offer(root);
        q.offer(null);
        long max = Long.MIN_VALUE;
        while (!q.isEmpty()) {
            tmp = q.poll();
            if (null != tmp) {
                if (max < tmp.val) {
                    max = tmp.val;
                }
                if (null != tmp.left) {
                    q.offer(tmp.left);
                }
                if (null != tmp.right) {
                    q.offer(tmp.right);
                }
            }
            //the end of this row
            //相当于遍历每层要判断这层是否有元素，参见LC102
            else if (Long.MIN_VALUE != max) {
                res.add((int) max);
                max = Long.MIN_VALUE;
                q.offer(null);
            }
        }
        return res;
    }

    //DFS
    int height = 0;
    Map<Integer, Integer> map = new HashMap();

    public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new ArrayList();
        if (null == root) {
            return res;
        }
        dfs(root, 0);
        for (int i = 0; i < map.size(); i++) {
            res.add(map.get(i));
        }
        return res;
    }

    private void dfs(TreeNode root, int level) {
        if (null == root) {
            return;
        }
        height = Math.max(height, level);
        //the max val of current row
        int tmpMaxValue = Math.max(map.getOrDefault(level, Integer.MIN_VALUE), root.val);
        map.put(level, tmpMaxValue);

        dfs(root.left, level + 1);
        dfs(root.right, level + 1);
    }
}