513.找树左下角的值

难度：中等

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

示例1：

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

示例2：

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

提示：

二叉树的节点个数的范围是 [0,104]
-231 <= Node.val <= 231 - 1

广度优先搜索法（BFS）

这道题和 102 题很类似，改动在于在每一层的遍历过程中，把该层的元素进行最大值记录，得到最大值后，再将其放进 result 列表中。

层序遍历一个二叉树。就是从左到右、一层一层地去遍历二叉树。这种遍历的方式需要借用一个辅助数据结构即队列来实现。

队列具有 先进先出 的特性，符合层序遍历的逻辑。这种层序遍历的方式就是图论中的广度优先遍历，只不过我们应用在了二叉树上。

算法流程：

处理特例：若根节点为空，则返回空列表
根节点入队
BFS 循环：判断队列是否为空。如果不为空，说明还有节点需要遍历
1. 初始化当前层的节点个数 currentLevelSize 为队列的大小
2. 使用一个内层循环，遍历当前层的节点。循环次数为当前层的节点个数 currentLevelSize
  1. 从队列中取出一个节点 current，将其元素值进行最大值比较
  2. 如果当前节点有左子节点，将左子节点入队
  3. 如果当前节点有右子节点，将右子节点入队
3. 将得到的该层最大值加入结果列表 result 中
4. 此时队列中已经把当前层的节点都出队了，同时把下一层的节点都入队了，因此队列大小刚好变成了下一层的节点个数
返回结果列表

代码展示

java

public List<Integer> largestValues(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    // 若根节点为空，则返回空列表
    if (root == null) {
        return result;
    }
    Deque<TreeNode> queue = new LinkedList<>();
    // 根节点入队
    queue.add(root);
    // BFS 循环
    while (!queue.isEmpty()) {
        int currentLayerSize = queue.size();
        Integer maxValue = Integer.MIN_VALUE;
        // 这里一定要使用固定大小currentLayerSize，不要使用queue.size()，因为queue不停地出队入队，所以其大小是不断变化的
        for (int i = 0; i < currentLayerSize; i++) {
            TreeNode current = queue.poll();
            maxValue = Math.max(maxValue, current.val);
            if (current.left != null) {
                queue.add(current.left);
            }
            if (current.right != null) {
                queue.add(current.right);
            }
        }
        result.add(maxValue);
    }
    return result;
}

时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。

空间复杂度：O(n)，最差情况下，即当树为满二叉树时，最多有 (n+1)/2 个树节点同时在 queue 中，故使用 O(n) 大小的额外空间。

总结

Integer.MIN_VALUE 是在 Java 中整型变量的最小值。

513.找树左下角的值 ​

广度优先搜索法（BFS） ​

代码展示 ​

总结 ​

513.找树左下角的值

广度优先搜索法（BFS）

代码展示

总结