。 N 叉樹郵購遍歷

590。 N 叉樹後序遍歷

難度：簡單

主題： 堆疊、樹、深度優先搜尋

給定n叉樹的根，回傳其節點值的後序遍歷。

Nary-Tree 輸入序列化以其層級順序遍歷來表示。每組子項均由空值分隔（請參閱範例）

範例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 ,空,13,空,空,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 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是。 N 叉樹郵購遍歷的詳細內容。更多資訊請關注PHP中文網其他相關文章！