二分木が対称であるかどうかを確認する方法は？
1. 序章
コンピュータサイエンスでは、二分木は、各ノードに最大2つの子を持つデータ構造です。
このチュートリアルでは、二分木が対称であるかどうかを確認する方法を示します。
2. 対称二分木
二分木では、各ノードに2つのサブツリー（左サブツリーと右サブツリー）があります。 サブツリーは、空、単一ノード、または別のバイナリツリーにすることができます。ルートノードの左側のサブツリーが右側のサブツリーのミラー反射である場合、バイナリツリーは対称です。たとえば、次のバイナリツリーは対称です。 ：次の二分木は対称ではありませんが、2つのサブツリーは同じツリー構造になっています。
3. 再帰的ソリューション
対称的な定義に基づいて、次のルールを使用して、2つの二分木が相互に鏡像であるかどうかを確認できます。
- 2つのルートノードの値は同じです
- 一方のルートノードの左側のサブツリーは、もう一方のルートノードの右側のサブツリーの鏡像です。
これらの条件を再帰的アルゴリズムに変換するのは簡単です。
このアルゴリズムでは、再帰関数、を使用して、2つの二分木が相互に鏡像であるかどうかを確認します。 まず、入力バイナリツリーの少なくとも1つが空である場合を処理するために、いくつかの健全性チェックを実行します。 次に、関数を再帰的に呼び出すことにより、2つの空でないツリーに対称ルールを適用します。
高レベルでは、入力バイナリツリーの左側のサブツリーと右側のサブツリーで関数を呼び出すことができます。 入力ツリー全体を1回トラバースするため、このアルゴリズムの実行時間は、です。ここで、はツリー内のノードの総数です。
4. 反復ソリューション
二分木をレベルごとにトラバースすることで、この問題を反復的に解決することもできます。
queue データ構造を使用して、このツリートラバーサルアルゴリズムを実装できます。
この反復アルゴリズムでは、最初にルートノードの2つの子を含むキューを作成します。 次に、ループの各反復で、キューから2つのノードを抽出し、それらの値を比較します。 また、2つのノードの右と左の子は、将来の対称検出のために逆の順序でキューに挿入されます。 すべてのツリーノードをトラバースするか、ツリーが対称でないことが検出されるまで、このプロセスを続行します。
再帰的ソリューションと同じように、入力ツリー全体を1回トラバースします。 したがって、反復アルゴリズムの実行時間は、です。ここで、はツリー内のノードの総数です。
5. 結論
このチュートリアルでは、対称二分木のいくつかの例を示しました。 また、二分木が線形時間で対称であるかどうかを検出できる2つのアルゴリズムについても説明しました。
