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

🟠   🔖  树 深度优先搜索 广度优先搜索 二叉树  🔗 力扣 LeetCode

题目

Given the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed).

Example 1:

Input: root = [1,3,2,5,3,null,9]

Output: [1,3,9]

Example 2:

Input: root = [1,2,3]

Output: [1,3]

Constraints:

• The number of nodes in the tree will be in the range [0, 104].
• -231 <= Node.val <= 231 - 1

题目大意

给定一棵二叉树的根节点 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 来找到每行的最大值。

1. 初始化：

   • 如果树为空，直接返回空数组 res。
   • 使用一个队列 queue 来存储当前层的节点，从根节点 root 开始。

2. 遍历每一层：

   • 使用 queue.length 确定当前层的节点数量 len。
   • 初始化一个变量 max 为负无穷大，用于记录该层节点的最大值。

3. 处理每个节点：

   • 从队列中逐个取出当前层的节点，并更新该层的最大值。
   • 将该节点的左右子节点加入队列，以供下一层遍历。

4. 记录结果：

   • 将该层的最大值 max 添加到结果数组 res。

5. 继续下一层：

   • 循环执行以上步骤，直到队列为空，即所有层遍历完毕。

复杂度分析

• 时间复杂度：O(n)，每个节点访问一次，总共有 n 个节点。
• 空间复杂度：O(w)，w 为树的最大宽， 最多同时存储一层的节点。

代码

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var largestValues = function (root) {
	let res = [];
	if (!root) return res; // 如果树为空，直接返回

	let queue = [root]; // 初始化队列，包含根节点

	while (queue.length) {
		let max = -Infinity;
		const len = queue.length;

		// 遍历本层所有节点
		for (let i = 0; i < len; i++) {
			const node = queue.shift();
			max = Math.max(node.val, max); // 更新本层最大值
			if (node.left) queue.push(node.left);
			if (node.right) queue.push(node.right);
		}

		// 将本层最大值加入结果数组
		res.push(max);
	}

	return res;
};