144. Binary Tree Preorder Traversal

Easy

Description

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

Example:

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

Intuition#

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

前序遍歷順序為 Root -> Left -> Right
迭代版本用 Stack，注意先壓入右子節點再壓左子節點（因為 Stack 是 LIFO）

Approaches#

1: Recursive DFS#

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

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

⭐ 2: Iterative with Stack#

概念: 用 Stack 模擬，彈出節點時處理，先壓右再壓左確保左先被處理
時間複雜度: O(n)
空間複雜度: O(h)

class Solution {
    fun preorderTraversal(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.right?.let { stack.addLast(it) }
            node.left?.let { stack.addLast(it) }
        }
        return result
    }
}

🔑 Takeaways#

Pattern: 樹的遍歷 — 前序遍歷在序列化、複製樹等場景常用
關鍵技巧: 迭代前序遍歷的 Stack 中，先壓右再壓左，保證左子樹先被處理