。二元樹後序遍歷

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 類別定義二元樹中的節點，包括其值、左子節點和右子節點。

• postorder遍歷函數：

  • 我們初始化一個空的結果陣列和一個堆疊。
  • 我們使用 while 循環，只要堆疊不為空或目前節點不為空，循環就會繼續。
  • 如果目前節點不為空，我們將其壓入堆疊並移至其左子節點。
  • 如果目前節點為空，我們檢查棧頂節點。如果它有一個我們還沒有訪問過的右孩子，我們就會移動到右孩子。否則，我們將節點的值加到結果數組中並將其從堆疊中彈出。

這種迭代方法模擬了遞歸後序遍歷，而不使用系統遞歸，從而更加節省記憶體。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

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

• 領英
• GitHub

以上是。二元樹後序遍歷的詳細內容。更多資訊請關注PHP中文網其他相關文章！