侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-06-24 / 0 评论 / 0 点赞 / 36 阅读 / 234 字 / 正在检测是否收录...

题目

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


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

示例1:

image-20220624003118794

输入: 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);
    }
}
0

评论区