Binary Tree Inorder Traversal (DFS)

LC 94 題意

• 給定一棵二元樹，回傳其中序遍歷 (Left → Root → Right)。
• Example
  Input: [1,null,2,3]
  Output: [1,3,2]

thoughts

• 遞迴 (DFS)：最直覺方式。
• 迭代 (Stack)：手動模擬遞迴堆疊。

Kotlin — 遞迴

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

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
    }
}

Kotlin — 迭代

class Solution {
    fun inorderTraversal(root: TreeNode?): List<Int> {
        val stack = ArrayDeque<TreeNode>()
        val result = mutableListOf<Int>()
        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
    }
}

Follow-up

• 若要改成 Preorder 或 Postorder 怎麼改？
• 若不使用遞迴與 Stack（O(1) 空間）？（→ Morris Traversal）
• 若節點含有 parent pointer，如何反向遍歷？