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

難度：中等

主題：樹、深度優(yōu)先搜索、廣度優(yōu)先搜索、二叉樹

給定二叉樹的根，返回樹中每一行中最大值的數組（0索引）。

示例1：

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

示例2：

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

約束：

• 樹中的節(jié)點數量將在 [0, 10⁴] 范圍內。
• -2³¹ 31 - 1

解決方案：

問題“查找每個樹行中的最大值”需要識別二叉樹的每個級別（行）中存在的最大值。給定一棵二叉樹，目標是逐行遍歷樹并收集每一行的最大值。這個問題涉及基本的樹遍歷技術，例如廣度優(yōu)先搜索（BFS）或深度優(yōu)先搜索（DFS）。

要點

1. 樹遍歷：解決方案涉及遍歷二叉樹的所有級別，以確定每個級別的最大值。
2. 廣度優(yōu)先搜索（BFS）：BFS適合逐級遍歷，可以簡化查找每一行中最大值的過程。
3. 約束：處理邊緣情況，例如空樹和約束范圍內具有大或小整數值的節(jié)點。

接近

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

• 逐層遍歷樹。
• 對于每個級別，跟蹤最大值。

或者，也可以使用DFS：

• 遞歸遍歷樹并維護每個深度處最大值的記錄。

計劃

1. 初始化一個數組來存儲每行的最大值。
2. 使用隊列進行BFS遍歷：
   • 從根節(jié)點開始。
   • 在移動到下一個級別之前處理當前級別的所有節(jié)點。
3. 每個級別：
   • 迭代所有節(jié)點并找到最大值。
   • 將此值添加到結果數組中。
4. 遍歷完成后返回結果數組。

解決步驟

1. 檢查輸入：如果根為空，則返回空數組。
2. 設置 BFS：
   • 使用以根節(jié)點初始化的隊列。
   • 初始化一個空結果數組。
3. 遍歷級別：
   • 對于每個級別，跟蹤最大值。
   • 將子節(jié)點添加到下一級隊列中。
4. 更新結果：
   • 將每個級別的最大值附加到結果數組中。
5. 返回結果：返回包含每行最大值的結果數組。

讓我們用 PHP 實現(xiàn)這個解決方案：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：節(jié)點值：[1] → 最大值：1。
2. 級別 1：節(jié)點值：[3, 2] → 最大值：3。
3. 級別 2：節(jié)點值：[5,3,9] → 最大值：9。 #### 輸出：[1, 3, 9].

時間復雜度

• BFS 遍歷：每個節(jié)點處理一次 → O(n).
• 尋找最大值：在遍歷過程中完成 → 每層 O(1)。
• 總計：O(n)。

空間復雜度

• 隊列存儲：最多樹的寬度（最大級別的節(jié)點數）→ O(w) 其中 w 是樹的最大寬度。

示例輸出

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

輸出：[1,3,9].

這種基于 BFS 的解決方案以線性時間復雜度有效計算每個樹行中的最大值。它可以有效地處理大樹、負值和空樹等邊緣情況。

聯(lián)系鏈接

如果您發(fā)現(xiàn)本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是。查找每個樹行中的最大值的詳細內容。更多信息請關注PHP中文網其他相關文章！