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

145。二分木事後探索

難易度: 簡単

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

バイナリ ツリーのルートを指定すると、そのノードの値の事後探索を返します。

例 1:

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

例 2:

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

例 3:

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

制約:

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

解決策:

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

このソリューションを PHP で実装してみましょう: 145。二分木事後探索

<?php
// Definition for a binary tree node.
class TreeNode {
    public $val = null;
    public $left = null;
    public $right = null;
    public function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}
/**
* @param TreeNode $root
* @return Integer[]
*/
function postorderTraversal($root) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:

// Example 1
$root1 = new TreeNode(1);
$root1->right = new TreeNode(2);
$root1->right->left = new TreeNode(3);
print_r(postorderTraversal($root1)); // Output: [3, 2, 1]

// Example 2
$root2 = null;
print_r(postorderTraversal($root2)); // Output: []

// Example 3
$root3 = new TreeNode(1);
print_r(postorderTraversal($root3)); // Output: [1]
?>

説明：

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

• postorderTraversal 関数:

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

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

連絡先リンク

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

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

• LinkedIn
• GitHub

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