94. Binary Tree Inorder Traversal

Easy

Description

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

Example:

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

Intuition#

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

中序遍歷是三種基本遍歷之一，順序為 Left -> Root -> Right
遞迴寫法最直覺，迭代寫法需要用 Stack 模擬遞迴過程
對 BST 做中序遍歷會得到排序結果

Approaches#

1: Recursive DFS#

概念: 遞迴先走左子樹，再加入當前節點值，最後走右子樹
時間複雜度: O(n)，每個節點訪問一次
空間複雜度: O(h)，遞迴堆疊深度，h 為樹高

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

⭐ 2: Iterative with Stack#

概念: 用 Stack 模擬遞迴，不斷往左走到底，再回頭處理節點並轉向右子樹
時間複雜度: O(n)
空間複雜度: O(h)

class Solution {
    fun inorderTraversal(root: TreeNode?): List<Int> {
        val result = mutableListOf<Int>()
        val stack = ArrayDeque<TreeNode>()
        var curr = root
        while (curr != null || stack.isNotEmpty()) {
            while (curr != null) {
                stack.addLast(curr)
                curr = curr.left
            }
            curr = stack.removeLast()
            result.add(curr.`val`)
            curr = curr.right
        }
        return result
    }
}

🔑 Takeaways#

Pattern: 樹的遍歷 — 中序遍歷是 BST 相關問題的基礎
關鍵技巧: 迭代版本的核心是「一路向左壓棧，彈出時處理並轉右」，這個模式在很多樹的題目中都會用到