。查找每个树行中的最大值

515。找到每行树中的最大值

难度：中等

主题：树、深度优先搜索、广度优先搜索、二叉树

给定二叉树的根，返回树中每一行中最大值的数组（0索引）。

示例1：

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

示例2：

• 输入： root = [1,2,3]
• 输出： [1,3]

约束：

• 树中的节点数量将在 [0, 10⁴] 范围内。
• -2³¹ 31 - 1

解决方案：

问题“查找每个树行中的最大值”需要识别二叉树的每个级别（行）中存在的最大值。给定一棵二叉树，目标是逐行遍历树并收集每一行的最大值。这个问题涉及基本的树遍历技术，例如广度优先搜索（BFS）或深度优先搜索（DFS）。

要点

1. 树遍历：解决方案涉及遍历二叉树的所有级别，以确定每个级别的最大值。
2. 广度优先搜索（BFS）：BFS适合逐级遍历，可以简化查找每一行中最大值的过程。
3. 约束：处理边缘情况，例如空树和约束范围内具有大或小整数值的节点。

接近

查找每行中最大值的最直接方法是使用 BFS:

• 逐层遍历树。
• 对于每个级别，跟踪最大值。

或者，也可以使用DFS：

• 递归遍历树并维护每个深度处最大值的记录。

计划

1. 初始化一个数组来存储每行的最大值。
2. 使用队列进行BFS遍历：
   • 从根节点开始。
   • 在移动到下一个级别之前处理当前级别的所有节点。
3. 每个级别：
   • 迭代所有节点并找到最大值。
   • 将此值添加到结果数组中。
4. 遍历完成后返回结果数组。

解决步骤

1. 检查输入：如果根为空，则返回空数组。
2. 设置 BFS：
   • 使用以根节点初始化的队列。
   • 初始化一个空结果数组。
3. 遍历级别：
   • 对于每个级别，跟踪最大值。
   • 将子节点添加到下一级队列中。
4. 更新结果：
   • 将每个级别的最大值附加到结果数组中。
5. 返回结果：返回包含每行最大值的结果数组。

让我们用 PHP 实现这个解决方案：515。找到每行树中的最大值

<?php
// Definition for a binary tree node.
class TreeNode {
    public $val = null;
    public $left = null;
    public $right = null;
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

/**
 * @param TreeNode $root
 * @return Integer[]
 */
function largestValues($root) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$root = new TreeNode(1);
$root->left = new TreeNode(3);
$root->right = new TreeNode(2);
$root->left->left = new TreeNode(5);
$root->left->right = new TreeNode(3);
$root->right->right = new TreeNode(9);

print_r(largestValues($root)); // Output: [1, 3, 9]
?>

解释：

输入：[1,3,2,5,3,null,9]

1. 级别 0：节点值：[1] → 最大值：1。
2. 级别 1：节点值：[3, 2] → 最大值：3。
3. 级别 2：节点值：[5,3,9] → 最大值：9。 #### 输出：[1, 3, 9].

时间复杂度

• BFS 遍历：每个节点处理一次 → O(n).
• 寻找最大值：在遍历过程中完成 → 每层 O(1)。
• 总计：O(n)。

空间复杂度

• 队列存储：最多树的宽度（最大级别的节点数）→ O(w) 其中 w 是树的最大宽度。

示例输出

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

输出：[1,3,9].

这种基于 BFS 的解决方案以线性时间复杂度有效计算每个树行中的最大值。它可以有效地处理大树、负值和空树等边缘情况。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是。查找每个树行中的最大值的详细内容。更多信息请关注PHP中文网其他相关文章！