。 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⁴] の範囲内です。
• -100 4
• n 進木の高さは 1000 以下です。

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

解決策:

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

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

<?php
//Definition for a Node.
class Node {
    public $val = null;
    public $children = [];

    public function __construct($val) {
        $this->val = $val;
    }
}

/**
 * @param Node $root
 * @return integer[]
 */
function postorder($root) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1:
$root1 = new Node(1);
$root1->children = [
    $node3 = new Node(3),
    new Node(2),
    new Node(4)
];
$node3->children = [
    new Node(5),
    new Node(6)
];

print_r(postorder($root1)); // Output: [5, 6, 3, 2, 4, 1]

// Example 2:
$root2 = new Node(1);
$root2->children = [
    new Node(2),
    $node3 = new Node(3),
    $node4 = new Node(4),
    $node5 = new Node(5)
];
$node3->children = [
    $node6 = new Node(6),
    $node7 = new Node(7)
];
$node4->children = [
    $node8 = new Node(8)
];
$node5->children = [
    $node9 = new Node(9),
    $node10 = new Node(10)
];
$node7->children = [
    new Node(11)
];
$node8->children = [
    new Node(12)
];
$node9->children = [
    new Node(13)
];
$node11 = $node7->children[0];
$node11->children = [
    new Node(14)
];

print_r(postorder($root2)); // Output: [2, 6, 14, 11, 7, 3, 12, 8, 4, 13, 9, 10, 5, 1]
?>

説明：

1. 初期化:

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

2. トラバーサル:

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

3. 結果:

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

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

連絡先リンク

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

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

• LinkedIn
• GitHub

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