145. Binary Tree Postorder Traversal

Easy

Description

給定一棵二元樹的根節點，回傳其後序遍歷 (Postorder Traversal) 的節點值列表。後序遍歷順序為：左子樹 -> 右子樹 -> 根。

Example:

Input: root = [1,null,2,3] Output: [3,2,1]

Intuition#

後序遍歷：先遞迴走左、右子樹，最後才處理當前節點。

後序遍歷順序為 Left -> Right -> Root
迭代版本可以利用「反轉的前序遍歷」技巧：前序是 Root -> Left -> Right，改為 Root -> Right -> Left 後反轉即得 Left -> Right -> Root

Approaches#

1: Recursive DFS#

概念: 遞迴先走左子樹，再走右子樹，最後處理當前節點
時間複雜度: O(n)
空間複雜度: O(h)

class Solution {
    fun postorderTraversal(root: TreeNode?): List<Int> {
        val result = mutableListOf<Int>()
        fun dfs(node: TreeNode?) {
            if (node == null) return
            dfs(node.left)
            dfs(node.right)
            result.add(node.`val`)
        }
        dfs(root)
        return result
    }
}

⭐ 2: Iterative (反轉前序)#

概念: 修改前序遍歷為 Root -> Right -> Left，最後將結果反轉即為後序遍歷
時間複雜度: O(n)
空間複雜度: O(n)，需要存放完整結果後反轉

class Solution {
    fun postorderTraversal(root: TreeNode?): List<Int> {
        val result = mutableListOf<Int>()
        if (root == null) return result
        val stack = ArrayDeque<TreeNode>()
        stack.addLast(root)
        while (stack.isNotEmpty()) {
            val node = stack.removeLast()
            result.add(node.`val`)
            node.left?.let { stack.addLast(it) }
            node.right?.let { stack.addLast(it) }
        }
        return result.reversed()
    }
}

🔑 Takeaways#

Pattern: 樹的遍歷 — 後序遍歷常用於需要先處理子樹再處理父節點的場景（如刪除樹、計算子樹大小）
關鍵技巧: 迭代後序遍歷可以透過「修改前序 + 反轉」的技巧簡化實作，避免複雜的雙棧或標記法