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é)點(diǎn)數(shù)量將在 [0, 10⁴] 範(fàn)圍內(nèi)。
• -2³¹ 31 - 1

解：

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

要點(diǎn)

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

接近

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

• 逐層遍歷樹。
• 對(duì)於每個(gè)級(jí)別，追蹤最大值。

或者，也可以使用DFS：

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

計(jì)畫

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

解決步驟

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

讓我們用 PHP 實(shí)作這個(gè)解：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. 等級(jí) 0：節(jié)點(diǎn)值：[1] → 最大值：1。
2. 等級(jí) 1：節(jié)點(diǎn)值：[3, 2] → 最大值：3。
3. 等級(jí) 2：節(jié)點(diǎn)值：[5,3,9] → 最大值：9。 #### 輸出：[1, 3, 9].

時(shí)間複雜度

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

空間複雜度

• 佇列儲(chǔ)存：最多樹的寬度（最大等級(jí)的節(jié)點(diǎn)數(shù)）→ O(w) 其中 w 是樹的最大寬度。

範(fàn)例輸出

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

輸出：[1,3,9].

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

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

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

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

• 領(lǐng)英
• GitHub

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