二分木の高さを求める反復法

二分木はデータ構造です。バイナリ ツリーの各ノードには、0、1、または 2 つのノードが含まれます。したがって、バイナリ ツリーには複数のレベルを含めることができます。

ここでは、ループを使用してバイナリ ツリーの高さを見つける反復コードを記述する必要があります。二分木のレベルの総数は、二分木の高さを表します。あるいは、ルート ノードからのバイナリ ツリーの最大の深さがバイナリ ツリーの高さであるとも言えます。

問題文 - 二分木が与えられています。特定の二分木の高さを見つけるには、反復法を使用する必要があります。

方法1

上で述べたように、バイナリ ツリーの高さは、バイナリ ツリーのレベルの総数に等しくなります。キュー データ構造を使用して、各レベルの各ノードを反復処理し、ツリーの最大の深さを見つけます。

＃＃＃アルゴリズム＃＃＃

ステップ 1

- 「treeNode」クラスを定義し、「val」整数変数を追加します。また、クラス内に「左」ポインタと「右」ポインタを定義します。

ステップ 2

- createNode() 関数を定義して、ツリーの新しいノードを作成します。新しいtreeNodeを作成し、パラメータ値で「val」を初期化し、左右のポインタをnull値で初期化します。最後に新しく作成したノードを返します。

ステップ 3

- findHeight() 関数は、バイナリ ツリーの高さを見つけるために使用されます。

ステップ 4

- 現在のレベルのすべてのノード、「treeHeight」、「n_cnt」変数、および「temp」ノードを格納する「levelqueue」キューを定義します。

ステップ 5

- ヘッド ノードが Null の場合は、0 を返します。

ステップ 6

- ヘッド ノードを「levelQueue」にプッシュします。

ステップ 7

- 「while」ループを使用して、「levelQueue」が空になるまで繰り返します。

ステップ 8

- 「treeHeight」を 1 だけ増やし、現在のレベルのノードの総数を表すキューのサイズで「n_cnt」を初期化します。

ステップ 9

- キューのすべての要素を反復処理します。

ステップ 9.1

- キューの最初の要素をポップします。

ステップ 9.2

- 現在のノードに左側の子ノードがある場合は、それをキューに挿入します。

ステップ 9.3

- 現在のノードに正しい子ノードがある場合は、それをキューに挿入します。

ステップ 9.4

- キューから最初のノードを削除します。

ステップ 10

- 「treeHeight」変数の値を返します。 ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー 時間計算量 - 各ノードを走査する O(N)。

スペースの複雑さ - O(N) キューにノードを格納しています。

反復手法は、問題を解決する場合、常に再帰的手法よりも高速です。ここでは、ループとキューを使用して、バイナリ ツリーの最大の深さまたは高さを繰り返し見つけます。ただし、プログラマは、バイナリ ツリーの高さを見つけるために再帰的メソッドをコーディングしようとする場合があります。

以上が二分木の高さを求める反復法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。