貪欲アルゴリズム: バイナリツリーを監視したい!

[[361051]]

バイナリツリーの問題の監視アドレス: https://leetcode-cn.com/problems/binary-tree-cameras/

バイナリツリーが与えられた場合、ツリーのノードにカメラを設置します。

ノード上の各カメラは、その親、それ自体、およびその直下の子を監視できます。

ツリーのすべてのノードを監視するために必要なカメラの最小数を計算します。

例1:

入力: [0,0,null,0,0]

出力: 1

説明: 図に示すように、すべてのノードを監視するには 1 台のカメラで十分です。

例2:

入力: [0,0,null,0,null,0,null,null,0]

出力: 2

説明: 木のすべてのノードを監視するには、少なくとも 2 台のカメラが必要です。上の画像は、カメラを配置するための有効な位置の 1 つを示しています。

ヒント：

• 与えられたツリー内のノードの数は [1, 1000] の範囲にあります。
• 各ノードの値は 0 です。

アイデア

この質問で最初に考えるべきことは、カメラを最小にするにはどのように配置するかということです。

タイトルの例から、実際にインスピレーションを得ることができます。タイトルの例では、カメラがリーフ ノードに配置されていないことがわかりました。

これは非常に重要な手がかりです。カメラは上層、中層、下層をカバーできます。カメラをリーフノードに配置すると、1 層のカバーが無駄になります。

したがって、カメラをリーフノードの親ノードの位置に配置することで、カメラのカバー範囲を最大限に活用できます。

すると、なぜヘッドノードから始めないのか、なぜリーフノードから始めるのかと疑問に思う生徒もいるかもしれません。

ヘッドノードにカメラを配置するかどうかによってカメラが 1 台節約され、リーフノードにカメラを配置するかどうかによってカメラの数が指数関数的に節約されるためです。

したがって、下から上に向かって、局所最適値、つまりリーフ ノードの親ノードにカメラを設置し、使用するカメラの数を最小限に抑え、全体的な最適値、つまり使用するカメラの数が最も少ないものを検討する必要があります。

局所最適解は、全体最適解につながります。反例が見つからない場合は、貪欲なアプローチに従ってください。

この時点での一般的な考え方は、リーフ ノードの親ノードに下から上に向かってカメラを配置し、バイナリ ツリーのヘッド ノードに到達するまで 2 つのノードごとにカメラを配置することです。

この問題には 2 つの難点があります。

1. 二分木の走査
2. 2ノードごとにカメラを配置する方法

トラバース順序を決定する

バイナリツリーで下から上に推論するにはどうすればよいでしょうか?

後順トラバーサル、つまり左、右、中央の順序を使用すれば、バックトラック処理中に下から上へ推論することができます。

後順序トラバーサル コードは次のとおりです。

 intトラバーサル(TreeNode* cur) { 
 
        // 空のノード、このノードはカバレッジを持っています
        if (終了条件) return ; 
 
整数  left = traversal(cur-> left ); // 左
整数  right = traversal(cur-> right ); // 右
 
        論理処理 //
戻る;
    }

上記のコードでは、左の子の戻り値と右の子の戻り値、つまり左と右を取得し、中間のノードの状態を推測していることに注意してください。

2ノードごとにカメラを配置する方法

このとき、状態転送式が必要になります。動的状態転送式と混同しないでください。この問題には最適な状態転送プロセスはありません。単純な状態転送だけです。

この状態がどのように転送されるかを見てみましょう。まず、各ノードが複数の状態になる可能性があるかどうかを見てみましょう。

3 つのタイプがあります。

• このノードはカバレッジがありません
• このノードにはカメラがあります
• このノードにはカバレッジがあります

表現する数字は 3 つあります。

• 0: ノードにカバレッジがありません
• 1: このノードにはカメラがあります
• 2: このノードはカバレッジを持っています

おそらく、4 番目のノードのステータスは見つかりません。

生徒の中には、このノードにカメラがないという 4 番目の状態があるのではないかと疑問に思う人もいるかもしれません。実際には、カメラがないということは、カバレッジもカバレッジもないことを意味するため、合計で 3 つの状態が存在します。

ツリーをトラバースする過程で、空のノードに遭遇するので、空のノードはどのような状態にあるかが問題になります。空のノードは、カバーされていないことを意味しますか? カメラがあることを意味しますか? それとも、カバーされていますか?

本質に戻ると、カメラの数を最小限に抑えるためには、リーフノードの親ノードにカメラを設置して、カメラの数を最小限に抑えるようにする必要があります。

すると、空のノードはカバーされていない状態にすることができないため、その場合はリーフ ノードにカメラを配置する必要があります。空のノードはカメラがある状態にすることができないため、その場合はリーフ ノードの親ノードにカメラを配置する必要はありません。代わりに、リーフ ノードの祖父母ノードにカメラを配置できます。

したがって、空のノードの状態のみをカバーすることができ、リーフノードの親ノードにカメラを配置できるようになります。

次は再帰的な関係です。

すると、再帰の終了条件は空のノードに遭遇することになり、その時点で 2 (カバー済み) を返すことになります。その理由は上で説明しました。

コードは次のとおりです。

 // 空のノード、このノードはカバレッジを持っています
cur == NULLの場合は2 を返します。

再帰関数と終了条件が決まりました。次は単層ロジック処理を見てみましょう。

主な状況は 4 つあります。

• ケース1: 左ノードと右ノードの両方がカバーされている

左の子はカバーされており、右の子もカバーされているため、中央のノードはカバーされていない状態になるはずです。

図に示すように:

968.バイナリツリーの監視 2

コードは次のとおりです。

 // 左ノードと右ノードの両方がカバーされます
左== 2 &&右== 2 の場合、 0 を返します。

• ケース2: 左ノードと右ノードの少なくとも1つがカバーされていない

次のような場合は、中間ノード（親ノード）にカメラを配置する必要があります。

• left == 0 && right == 0 左ノードと右ノードはカバーされていません
• left == 1 && right == 0 左のノードにはカメラがあり、右のノードにはカバレッジがありません
• left == 0 && right == 1 左のノードが覆われているかどうかに関係なく、右のノードがカメラです
• left == 0 && right == 2 左のノードはカバーされておらず、右のノードはカバーされている
• left == 2 && right == 0 左のノードはカバーされており、右のノードはカバーされていません

これは理解するのが難しくありません。結局のところ、カバーされていない子がある場合は、親ノードがカメラを配置する必要があります。

このとき、カメラの数は 1 つ増え、1 を返します。これは、カメラが中間ノードに配置されていることを意味します。

コードは次のとおりです。

 if (左== 0 ||右== 0 ) {
    結果++;
 1 を返します。
 }

• ケース3: 左と右のノードの少なくとも1つにカメラがある

次のような状況が発生した場合、左と右の子ノードの1つにカメラがあり、その親ノードは2（カバーされた状態）になります。

• left == 1 && right == 2 左のノードにはカメラがあり、右のノードにはカバレッジがあります
• left == 2 && right == 1 左のノードにはカバレッジがあり、右のノードにはカメラがあります
• left == 1 && right == 1 左ノードと右ノードの両方にカメラがある

コードは次のとおりです。

左== 1 ||右== 1の場合、 2 を返します。

このコードから、left == 1、right == 0 の場合はどうなるかがわかります。実際、この条件は、図に示すように、ケース 2 で判断されています。

968.バイナリツリーの監視 1

この状況は、ほとんどの学生が簡単に混乱してしまう状況でもあります。

• ケース4: ヘッドノードがカバーされていない

上記の処理がすべて完了し、再帰が終了した後でも、図に示すように、ヘッドノードがカバーされていない状況がまだ発生する可能性があります。

968.バイナリツリーの監視3

したがって、再帰が終了したら、ルート ノードを決定する必要があります。ルート ノードがカバーされていない場合は、result++ を使用します。コードは次のとおりです。

 int最小カメラカバー(TreeNode* ルート) {
    結果 = 0;
    if (traversal(root) == 0) { // ルートがカバーされていない
        結果++;
    }
結果を返します。
 }

上記の 4 つの状況を分析しましたが、コードはほぼ同じです。全体的なコードは次のとおりです。

(以下のコードコメントは非常に詳細です。状況を明確にするために、各ケースをリストします。)

C++ コード

// バージョン 1
クラスソリューション{
プライベート：
 int結果;
 intトラバーサル(TreeNode* cur) { 
 
        // 空のノード、このノードはカバレッジを持っています
        cur == NULLの場合は2 を返します。 
 
整数  left = traversal(cur-> left ); // 左
整数  right = traversal(cur-> right ); // 右
 
        // ケース1
        // 左ノードと右ノードの両方がカバーされます
        左== 2 &&右== 2 の場合、 0 を返します。 
 
        // ケース2
        // left == 0 && right == 0 左と右のノードはカバーされていません
        // left == 1 && right == 0 左のノードにはカメラがあり、右のノードにはカバレッジがありません
        // left == 0 && right == 1 左のノードが覆われているかどうかに関係なく、右のノードがカメラです
        // left == 0 && right == 2 左のノードはカバーされておらず、右のノードはカバーされています
        // left == 2 && right == 0 左のノードはカバーされており、右のノードはカバーされていません
        if (左== 0 ||右== 0 ) {
            結果++;
 1 を返します。
        } 
 
        // ケース3
        // left == 1 && right == 2 左のノードにはカメラがあり、右のノードにはカバレッジがあります
        // left == 2 && right == 1 左のノードにはカバレッジがあり、右のノードにはカメラがあります
        // left == 1 && right == 1 左ノードと右ノードの両方にカメラがある
        //その他のケースは前のコードでカバーされています
        左== 1 ||右== 1 の場合、 2 を返します。 
 
        // 上記のコードではelseを使用しませんでした。主にさまざまな分岐条件を示し、読者がコードを理解しやすくするためです。
        // このreturn -1 ロジックはここでは使用しません。
 -1 を返します。
    } 
 
公共：
 int最小カメラカバー(TreeNode* ルート) {
        結果 = 0;
        // ケース4
        if (traversal(root) == 0) { // ルートがカバーされていない
            結果++;
        }
結果を返します。
    }
 };

上記のコードに基づいて、コードは次のように簡略化されます。

 // バージョン 2
クラスソリューション{
プライベート：
 int結果;
 intトラバーサル(TreeNode* cur) {
        cur == NULLの場合は2 を返します。
整数  left = traversal(cur-> left ); // 左
整数  right = traversal(cur-> right ); // 右
        左== 2 &&右== 2 の場合、 0 を返します。
そうでない場合 (左== 0 ||右== 0 ) {
            結果++;
 1 を返します。
        }それ以外  2を返します。
    }
公共：
 int最小カメラカバー(TreeNode* ルート) {
        結果 = 0;
        if (traversal(root) == 0) { // ルートがカバーされていない
            結果++;
        }
結果を返します。
    }
 };

こんなに短くなるなんて、驚かれるかもしれません。実際、これはバージョン 1 に基づいており、else を使用していくつかの状況を直接カバーしています。

この問題の解決方法については、インターネット上で神レベルのコードが多数見つかりますが、どれも明確に説明されていません。コードを直接見ると、ますます混乱するでしょう。そのため、バージョン 1 のコードを段階的に実行することをお勧めします。バージョン 2 は役に立ちません。

要約する

この問題の難しさは、まず貪欲な考え方を考え、次に推論をたどって述べることです。

実際、バイナリ ツリー上の状態推論の難しさはより高いレベルにあり、バイナリ ツリーの非常に熟練した操作が必要です。

この記事はWeChatの公開アカウント「Code Thoughts」から転載したもので、以下のQRコードからフォローできます。この記事を転載する場合は、Code Thoughts の公開アカウントにご連絡ください。