515。求每行樹中的最大值

難度：中

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

給定二元樹的根，回傳樹中每一行中最大值的陣列（0索引）。

範(fàn)例1：

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

範(fàn)例2：

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

約束：

• 樹中的節(jié)點數(shù)量將在 [0, 10⁴] 範(fàn)圍內(nèi)。
• -2³¹ 31 - 1

解：

問題「找出每個樹行中的最大值」需要辨識二元樹的每個層級（行）中存在的最大值。給定一棵二元樹，目標(biāo)是逐行遍歷樹並收集每一行的最大值。這個問題涉及基本的樹遍歷技術(shù)，例如廣度優(yōu)先搜尋（BFS）或深度優(yōu)先搜尋（DFS）。

要點

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

接近

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

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

或者，也可以使用DFS：

• 遞歸遍歷樹並維護(hù)每個深度處最大值的記錄。

計畫

1. 初始化一個陣列來儲存每行的最大值。
2. 使用佇列進(jìn)行BFS遍歷：
   • 從根節(jié)點開始。
   • 在移動到下一個層級之前處理目前層級的所有節(jié)點。
3. 每個等級：
   • 迭代所有節(jié)點並找到最大值。
   • 將此值加到結(jié)果陣列中。
4. 遍歷完成後傳回結(jié)果陣列。

解決步驟

1. 檢查輸入：如果根為空，則傳回空數(shù)組。
2. 設(shè)定 BFS：
   • 使用以根節(jié)點初始化的佇列。
   • 初始化一個空結(jié)果陣列。
3. 遍歷等級：
   • 對於每個級別，追蹤最大值。
   • 將子節(jié)點加入到下一層佇列。
4. 更新結(jié)果：
   • 將每個層級的最大值附加到結(jié)果陣列中。
5. 傳回結(jié)果：傳回包含每行最大值的結(jié)果陣列。

讓我們用 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：節(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é)點數(shù)）→ O(w) 其中 w 是樹的最大寬度。

範(fàn)例輸出

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

輸出：[1,3,9].

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

聯(lián)絡(luò)連結(jié)

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

如果您想要更多類似的有用內(nèi)容，請隨時關(guān)注我：

• 領(lǐng)英
• GitHub

以上是。找出每個樹行中的最大值的詳細(xì)內(nèi)容。更多資訊請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！