サブツリー削除クエリ後のバイナリ ツリーの高さ

2458。サブツリー削除クエリ後のバイナリ ツリーの高さ

難易度: 難しい

トピック: 配列、ツリー、深さ優先検索、幅優先検索、バイナリ ツリー

n 個のノードを持つバイナリーツリーのルートが与えられます。各ノードには 1 から n までの一意の値が割り当てられます。サイズ m の配列クエリも与えられます。

ツリー上で m 個の 独立した クエリを実行する必要があります。i ^番目 のクエリでは次の処理を実行します。

• 値 queries[i] を持つノードをルートとするサブツリーをツリーから削除します。クエリ[i]がルートの値と等しくないことが保証されます。

サイズ m の配列の回答を返します。ここで、answer[i] は、i^番目のクエリを実行した後のツリーの高さです。

注:

• クエリは独立しているため、各クエリの後にツリーは初期状態に戻ります。
• ツリーの高さは、ルートからツリー内のノードまでの最長の単純なパスのエッジの数です。

例 1:

• 入力: ルート = [1,3,4,2,null,6,5,null,null,null,null,null,7]、クエリ = [4]
• 出力: [2]
• 説明: 上の図は、値 4 のノードをルートとするサブツリーを削除した後のツリーを示しています。
  • 木の高さは 2 (パス 1 -> 3 -> 2)。

例 2:

• 入力: ルート = [5,8,9,2,1,3,7,4,6​​]、クエリ = [3,2,4,8]
• 出力: [3,2,3,2]
• 説明: 次のクエリがあります:
  • 値 3 のノードをルートとするサブツリーを削除します。ツリーの高さは 3 になります (パス 5 -> 8 -> 2 -> 4)。
  • 値 2 のノードをルートとするサブツリーを削除します。ツリーの高さは 2 になります (パス 5 -> 8 -> 1)。
  • 値 4 のノードをルートとするサブツリーを削除します。ツリーの高さは 3 になります (パス 5 -> 8 -> 2 -> 6)。
  • 値 8 のノードをルートとするサブツリーを削除します。ツリーの高さは 2 になります (パス 5 -> 9 -> 3)。

制約:

• ツリー内のノードの数は n です。
• 2 5
• 1
• ツリー内の値はすべて 一意です。
• m == クエリの長​​さ
• 1 4)
• 1
• クエリ[i] != root.val

ヒント:

1. 1 から n までの各ノードの答えを事前計算し、O(1) で各クエリに答えてみます。
2. 各サブツリーの高さを計算した後、単一のツリー走査で答えを事前に計算できます。

解決策:

このソリューションでは、2 パスのアプローチが採用されています。

1. ツリー内の各ノードの高さを計算します。
2. クエリされた各ノードをルートとするサブツリーを削除した後、ツリーの最大高さを決定します。

このソリューションを PHP で実装してみましょう: 2458。サブツリー削除クエリ後のバイナリ ツリーの高さ

コードの内訳

1.クラス定義とプロパティ:

class Solution {

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

• valToMaxHeight: この配列には、各ノードのサブツリーを削除した後のツリーの最大高さが格納されます。
• valToHeight: この配列には、各ノードのサブツリーの高さが格納されます。

2.メイン関数:

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

• 関数treeQueriesは、ツリーのルートとクエリ配列を取得します。
• 最初に高さ関数を呼び出して、各ノードの高さを計算します。
• 次に、dfs (深さ優先検索) 関数を呼び出して、サブツリー削除後の最大の高さを計算します。
• 最後に、各クエリの結果を回答配列に入力します。

3.身長の計算:

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

• この関数は各ノードの高さを再帰的に計算します。
• ノードが null の場合、0 を返します。
• ノードの高さがすでに計算されている場合は、それをキャッシュ (valToHeight) から取得します。
• 左右の子の高さに基づいて高さを計算し、valToHeight に格納します。

4.最大高さの深さ優先検索:

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

• この関数は、DFS を実行して、各ノードのサブツリーが削除された後のツリーの最大高さを計算します。
• 現在のノードの現在の最大高さを valToMaxHeight に記録します。
• 左右のサブツリーの高さを計算し、それに応じて最大高さを更新します。
• 左と右の子に対して自分自身を再帰的に呼び出し、深さと最大の高さを更新します。

チュートリアルの例

例を段階的に見てみましょう。

入力例:

// 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 の木の高さ (ノード 7 だけ)
• 根元2:0(葉のノード)の木の高さ

高さの計算後、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 はツリー内のノードの数、 です。 m はクエリの数です。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上がサブツリー削除クエリ後のバイナリ ツリーの高さの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。