【递归, 层序遍历】在每个树行中找最大值

题目

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

---

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

示例1：

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

示例2：

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

提示：

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

解题

方法一：递归 二叉树层序遍历

思路

把二叉树进行一个层序的遍历，然后维护每一层最大元素（注意节点值数据范围）。

代码

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> ans = new ArrayList<Integer>();
        levelOrderTraversal(root, 0, ans);
        return ans;
    }

    private void levelOrderTraversal(TreeNode node, int level, List<Integer> ans) {
        if (node == null) return;
        if (level >= ans.size()) ans.add(node.val);
        else if (node.val >= ans.get(level)) ans.set(level, node.val);
        levelOrderTraversal(node.left, level + 1, ans);
        levelOrderTraversal(node.right, level + 1, ans);
    }
}