。バイナリ ツリー事後トラバーサル

145。バイナリツリーポストオーダートラバーサル

難易度:簡単

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

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

。

例1:

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

例 2:

• 入力:root = []
• 出力:[]

例 3:

• 入力:root = [1]
• 出力:[1]

制約:

• ツリー内のノードの数は[0, 100]の範囲内です。
• -100

解決策:

スタックを使用した反復アプローチを使用できます。事後走査は、左、右、ルートの順序に従います。

このソリューションを PHP で実装してみましょう:145。バイナリツリーポストオーダートラバーサル

リーリー

説明：

• TreeNode クラス:TreeNode クラスは、値、左の子、右の子を含むバイナリ ツリー内のノードを定義します。

• ポストオーダートラバーサル関数:

  • 空の結果配列とスタックを初期化します。
  • スタックが空でない限り、または現在のノードが null でない限り継続する while ループを使用します。
  • 現在のノードが null でない場合は、それをスタックにプッシュし、その左の子に移動します。
  • 現在のノードがnullの場合、スタックの最上位ノードをチェックします。まだ訪問していない適切な子がある場合は、適切な子に移動します。それ以外の場合は、ノードの値を結果配列に追加し、スタックからポップします。

この反復アプローチは、システム再帰を使用せずに再帰的な事後探索をシミュレートし、メモリ効率を高めます。

連絡先リンク

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

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

• リンクトイン
• GitHub

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