2458。子樹刪除查詢後二元樹的高度

難度：難

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

給定一個具有 n 個節(jié)點的 二元樹 的根。每個節(jié)點都被分配一個從 1 到 n 的唯一值。您還會獲得一個大小為 m 的陣列查詢。

您必須在樹上執(zhí)行 m 獨立 查詢，其中在第 i^th 查詢中執(zhí)行以下操作：

• 從樹中刪除以值為queries[i]的節(jié)點為根的子樹。 保證查詢[i]將不等於根的值。

傳回大小為m的陣列答案，其中answer[i]是執(zhí)行第i^第查詢後樹的高度。

注意：

• 查詢是獨立的，因此樹在每次查詢後都會回到其初始狀態(tài)。
• 樹的高度是從根到樹中某個節(jié)點的最長簡單路徑的邊數(shù)。

範例1：

• 輸入： root = [1,3,4,2,null,6,5,null,null,null,null,null,7]，查詢 = [4]
• 輸出： [2]
• 說明： 上圖顯示了刪除以值為 4 的節(jié)點為根的子樹後的樹。
  • 樹的高度為 2（路徑 1 -> 3 -> 2）。

範例2：

• 輸入： root = [5,8,9,2,1,3,7,4,6??]，查詢 = [3,2,4,8]
• 輸出： [3,2,3,2]
• 說明：我們有以下疑問：
  • 刪除以值為 3 的節(jié)點為根的子樹。樹的高度變成 3（路徑 5 -> 8 -> 2 -> 4）。
  • 刪除以值為 2 的節(jié)點為根的子樹。樹的高度變成 2（路徑 5 -> 8 -> 1）。
  • 刪除以值為 4 的節(jié)點為根的子樹。樹的高度變成 3（路徑 5 -> 8 -> 2 -> 6）。
  • 刪除以值為 8 的節(jié)點為根的子樹。樹的高度變成 2（路徑 5 -> 9 -> 3）。

約束：

• 樹中的節(jié)點數(shù)為n。
• 2 5
• 1
• 樹中的所有值都是唯一。
• m == requests.length
• 1 4)
• 1
• 查詢[i] != root.val

提示：

1. 嘗試預先計算從 1 到 n 的每個節(jié)點的答案，並在 O(1) 內回答每個查詢。
2. 計算每個子樹的高度後，可以在單次樹遍歷中預先計算答案。

解：

此解決方案採用了兩遍方法：

1. 計算樹中每個節(jié)點的高度。
2. 刪除以每個查詢節(jié)點為根的子樹後，確定樹的最大高度。

讓我們用 PHP 實作這個解：2458。子樹刪除查詢後二元樹的高度

代碼分解

1。類別定義與屬性：

class Solution {

    private $valToMaxHeight = [];
    private $valToHeight = [];

• valToMaxHeight：此陣列將儲存刪除每個節(jié)點的子樹後樹的最大高度。
• valToHeight：此陣列將儲存每個節(jié)點子樹的高度。

2。主要功能：

function treeQueries($root, $queries) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

• 函數(shù)treeQueries取得樹的根和查詢陣列。
• 它首先呼叫 height 函數(shù)來計算每個節(jié)點的高度。
• 然後，它呼叫 dfs（深度優(yōu)先搜尋）函數(shù)來計算子樹刪除後的最大高度。
• 最後，它用每個查詢的結果填入答案陣列。

3。高度計算：

private function height($node) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

• 此函數(shù)遞歸計算每個節(jié)點的高度。
• 如果節(jié)點為空，則回傳0。
• 如果節(jié)點的高度已經計算出來，它會從快取中檢索它（valToHeight）。
• 根據(jù)左右子節(jié)點的高度計算高度，並將其儲存在 valToHeight 中。

4。深度優(yōu)先搜尋最大高度：

private function dfs($node, $depth, $maxHeight) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

• 此函數(shù)執(zhí)行 DFS 來計算刪除每個節(jié)點的子樹後樹的最大高度。
• 它在 valToMaxHeight 中記錄目前節(jié)點的目前最大高度。
• 它計算左右子樹的高度並相應地更新最大高度。
• 它遞歸地呼叫自己的左右子節(jié)點，更新深度和最大高度。

範例演練

讓我們逐步看一下範例。

輸入範例：

// Tree Structure
//        1
//       / \
//      3   4
//     /   / \
//    2   6   5
//         \
//          7

$root = [1, 3, 4, 2, null, 6, 5, null, null, null, null, null, 7];
$queries = [4];

初始高度計算：

• 樹根的高度為1:3
• 樹根的高度為3：2
• 以 4:2 為根的樹的高度（以 6 和 5 為根的子樹的高度）
• 以 6:1 為根的樹的高度（僅節(jié)點 7）
• 以2:0為根的樹的高度（葉節(jié)點）

高度計算後，valToHeight 將如下圖所示：

class Solution {

    private $valToMaxHeight = [];
    private $valToHeight = [];

最大的 DFS：

• 對於根 (1)，刪除子樹 4 個葉子：
  • 左高度：2（以 3 為根）
  • 右高：1（以 5 為根）
• 因此，去掉 4 後的最大高度為 2。

查詢後結果陣列：

• 對於查詢 4，結果將是 [2]。

最終輸出

所提供輸入的結果將是：

function treeQueries($root, $queries) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

這種結構化方法確保我們在初始預處理後有效地計算必要的高度並在恆定時間內回答每個查詢。整體複雜度為O(n m)，其中n 是樹中的節(jié)點數(shù)， m 是樹中的節(jié)點數(shù)，

m

是查詢次數(shù)。

聯(lián)絡連結

如果您發(fā)現(xiàn)本系列有幫助，請考慮在 GitHub 上給

存儲庫

一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

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

GitHub

以上是子樹刪除查詢後二元樹的高度的詳細內容。更多資訊請關注PHP中文網其他相關文章！