2021-02-24 515. 在每个树行中找最大值

题目地址

https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row/submissions/

题目描述

您需要在二叉树的每一行中找到最大的值。

示例：
输入: 

          1
         / \
        3   2
       / \   \  
      5   3   9 

输出: [1, 3, 9]

思路

1. 和117. 填充每个节点的下一个右侧节点指针 II很相似, 在层次遍历过程中进行一层一层的遍历. 在每一层遍历过程中求这一层最大值, 然后放入结果集中.
2. 递归遍历, 传入参数level, 计算每一层的最大值.

题解

/**
 * Created by zcdeng on 2021/2/24.
 */
public class LargestValues {
    public static void main(String[] args) {
        int[] arr = {1,3,2,5,3,-1,9};
        TreeNode root = TreeNode.createTreeNode(arr);

        List<Integer> result = largestValues(root);
        System.out.println(result);

        result = largestValuesV2(root);
        System.out.println(result);
    }
    /**
     * 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：39 MB , 在所有 Java 提交中击败了8.66%的用户
     */
    private static List<Integer> largestValuesV2(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        doLargestValuesV2(root, result, 0);
        return result;
    }
    private static void doLargestValuesV2(TreeNode root, List<Integer> result, int level) {
        if (root != null) {
            if(result.size() > level) {
                result.set(level, Math.max(result.get(level), root.getValue()));
            } else {
                result.add(root.getValue());
            }
            doLargestValuesV2(root.getLeft(), result, level + 1);
            doLargestValuesV2(root.getRight(), result, level + 1);
        }
    }

    /**
     * 执行用时：2 ms, 在所有 Java 提交中击败了76.57%的用户
     * 内存消耗：38.8 MB, 在所有 Java 提交中击败了23.40%的用户
     */
    private static List<Integer> largestValues(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        List<Integer> result = new ArrayList<Integer>();
        while (!queue.isEmpty()) {
            int size = queue.size();
            int max = Integer.MIN_VALUE;
            while (size-- > 0) {
                TreeNode node = queue.poll();
                if (node.getLeft() != null) {
                    queue.add(node.getLeft());
                }
                if (node.getRight() != null) {
                    queue.add(node.getRight());
                }
                max = Math.max(max, node.getValue());
            }
            result.add(max);
        }
        return result;
    }
}