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

问题链接

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

问题描述

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

示例

解题思路

这道题比较简单，把结果存在map里，遍历二叉树即可。

代码示例（JAVA）

/**
 * 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) {
        Map<Integer, Integer> map = new HashMap<>();
        preOrder(root, map, 1);

        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < map.size(); i++) {
            result.add(map.get(i+1));
        }
        return result;
    }

    private void preOrder(TreeNode node, Map<Integer, Integer> map, int row) {
        if (node == null) {
            return;
        }

        Integer maxVal = map.get(row) == null ? Integer.MIN_VALUE : map.get(row);
        if (maxVal <= node.val) {
            map.put(row, node.val);
        }

        preOrder(node.left, map, row + 1);
        preOrder(node.right, map, row + 1);
    }
}

执行结果