LeetCode - #145 二叉樹的後序遍歷

攜手創作，共同成長！這是我參與「掘金日新計劃 · 8 月更文挑戰」的第10天，點選檢視活動詳情

前言

我們社群陸續會將顧毅（Netflix 增長黑客，《iOS 面試之道》作者，ACE 職業健身教練。）的 Swift 演算法題題解整理為文字版以方便大家學習與閱讀。

LeetCode 演算法到目前我們已經更新到 144 期，我們會保持更新時間和進度（週一、週三、週五早上 9:00 釋出），每期的內容不多，我們希望大家可以在上班路上閱讀，長久積累會有很大提升。

不積跬步，無以至千里；不積小流，無以成江海，Swift社群 伴你前行。如果大家有建議和意見歡迎在文末留言，我們會盡力滿足大家的需求。

難度水平：簡單

1. 描述

給你二叉樹的根節點 root ，返回它節點值的 後序 遍歷。

2. 示例

示例 1

輸入：root = [1,null,2,3] 輸出：[3,2,1]

示例 2

輸入：root = [] 輸出：[]

示例 3

輸入：root = [1] 輸出：[1]

約束條件：

• 樹中節點數目在範圍 [0, 100] 內
• -100 <= Node.val <= 100

3. 答案

```swift /* * * Definition for a binary tree node. * public class TreeNode { * public var val: Int * public var left: TreeNode? * public var right: TreeNode? * public init(_ val: Int) { * self.val = val * self.left = nil * self.right = nil * } * } /

class PostorderTraversal { func postorderTraversal(root: TreeNode?) -> [Int] { var res = Int var stack = TreeNode var node = root

    while !stack.isEmpty || node != nil {
        if node != nil {
            res.insert(node!.val, atIndex: 0)
            stack.append(node!)
            node = node!.right
        } else {
            node = stack.removeLast().left
        }
    }

    return res
}

} ```

• 主要思想：使用堆疊來幫助迭代樹，向右插入頭部。
• 時間複雜度： O(n)
• 空間複雜度： O(n)

該演算法題解的倉庫：LeetCode-Swift

點選前往 LeetCode 練習

關於我們

我們是由 Swift 愛好者共同維護，我們會分享以 Swift 實戰、SwiftUI、Swift 基礎為核心的技術內容，也整理收集優秀的學習資料。

後續還會翻譯大量資料到我們公眾號，有感興趣的朋友，可以加入我們。