【515.在每个树行中找最大值】_二叉树_day02

1 题目描述

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。515.在每个树行中找最大值

2 解题思路

二叉树层序遍历的拓展：

1. 借助队列que来解决这个问题，核心点就是在二叉树每一层上进行操作需要记住保存其左右节点之后的队列que的大小len。
2. 首先创建一个ArrayList列表res用来保存每一层节点中值最大的数。
3. 判断root是否为空null,为空则直接返回列表res，结束当前函数。非空则进行后续的操作。
4. 进入条件为队列que非空的当前型循环①，循环①内部：
   1） 记录此时队列que的大小为len, 设置一个用来临时比较的最大值max (MIN_VALUE)
   2）进入循环②内部：
   • 把队列que的节点弹出并赋给新节点node
   • 将node.val赋给一个新的int变量temp
   • max 取max和temp中的最大值
   • node有左右节点则加入队列que中
   • len–
     3）将每一层的max添加至目标res中
5. 返回最终的结果res

3 代码

public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null) return res;

        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        while(!que.isEmpty()){
            int len = que.size();
            int max = Integer.MIN_VALUE;
            while(len>0){
                TreeNode node = que.poll();
                int temp = node.val;
                max = Math.max(temp,max);
                if(node.left != null) que.offer(node.left);
                if(node.right != null) que.offer(node.right);
                len--;
            }
            res.add(max);
        }

        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

---