。 N-ary Tree通販トラバース

590。 N進木事後トラバーサ

難易度:簡単

トピック:スタック、ツリー、深さ優先検索

n 進木のルートを指定すると、そのノードの値の事後探索を返します。

Nary-Tree 入力シリアル化は、レベル順序のトラバーサルで表されます。子の各グループは null 値で区切られます (例を参照)

例1:

• 入力:root = [1,null,3,2,4,null,5,6]
• 出力:[5,6,3,2,4,1]

例 2:

• 入力:root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13 ,null,null,14]
• 出力:[2,6,14,11,7,3,12,8,4,13,9,10,5,1]

制約:

ツリー内のノードの数は[0, 100
• 4^{]の範囲内です。}
-100 4 n 進木の高さは 1000 以下です。

フォローアップ:再帰的な解決策は簡単ですが、反復的に実行できますか?

解決策:

再帰的と反復の両方でアプローチできます。フォローアップでは反復的な解決策が求められるため、それに焦点を当てます。ポストオーダートラバーサルとは、最初に子ノードにアクセスし、次に親ノードにアクセスすることを意味します。

このソリューションを PHP で実装してみましょう:

590。 N 分ツリー事後探索
リーリー

説明：

1. 初期化:

   スタックを作成し、その上にルートノードをプッシュします。
   最後の事後順序走査を保存する空の配列結果を作成します。

2. トラバーサル:

   スタックからノードをポップし、その値を結果配列の先頭に挿入します。
   すべての子をスタックにプッシュします。
   スタックが空になるまで続けます。

3. 結果:

   結果配列には、ループ終了後のノードがポストオーダーで含まれます。

この反復アプローチは、スタックを使用し、通常は再帰によって行われるプロセスを逆にすることで、ポストオーダートラバーサルを効果的にシミュレートします。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で

リポジトリ

にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとってとても意味のあるものになります！このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

リンクトイン
GitHub

以上が。 N-ary Tree通販トラバースの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。