. N-ary Tree Mail Order Traverse

590. N-ary Tree Postorder Traversa

Kesukaran: Mudah

Topik: Tindanan, Pokok, Carian Pertama Kedalaman

Memandangkan akar pokok n-ary, kembalikan laluan pasca pesanan nilai nodnya.

Siri input Nary-Tree diwakili dalam traversal tertib tahap mereka. Setiap kumpulan kanak-kanak dipisahkan dengan nilai nol (Lihat contoh)

Contoh 1:

• Input: punca = [1,null,3,2,4,null,5,6]
• Output: [5,6,3,2,4,1]

Contoh 2:

• Input: punca = [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]
• Output: [2,6,14,11,7,3,12,8,4,13,9,10,5,1]

Kekangan:

• Bilangan nod dalam pepohon adalah dalam julat [0, 100⁴].
• -100 <= Node.val <= 100⁴
• Ketinggian pokok n-ary adalah kurang daripada atau sama dengan 1000.

Susulan: Penyelesaian rekursif adalah remeh, bolehkah anda melakukannya secara berulang?

Penyelesaian:

Kita boleh mendekatinya secara rekursif dan berulang. Memandangkan susulan meminta penyelesaian berulang, kami akan menumpukan padanya. Traversal pasca pesanan bermaksud melawati nod kanak-kanak dahulu dan kemudian nod induk.

Mari laksanakan penyelesaian ini dalam PHP: 590. N-ary Tree Postorder Traversal

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]
?>





  
  
  Penjelasan:




Permulaan:


Buat tindanan dan tolak nod akar ke atasnya.
Buat hasil tatasusunan kosong untuk menyimpan traversal pesanan pos terakhir.



Perjalanan:


Letakkan nod daripada tindanan, masukkan nilainya pada permulaan tatasusunan hasil.
Tolak semua anak-anaknya ke atas timbunan.
Teruskan sehingga timbunan kosong.



Keputusan:


 Tatasusunan hasil akan mengandungi nod dalam pesanan selepas selepas gelung selesai.




Pendekatan berulang ini secara berkesan mensimulasikan traversal pasca pesanan dengan menggunakan tindanan dan membalikkan proses yang biasanya dilakukan secara rekursi.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:


LinkedIn
GitHub



          

            
  

            
        
Atas ialah kandungan terperinci . N-ary Tree Mail Order Traverse. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!