二元樹走訪 (Binary Tree Traversal)#

走訪順序記憶法#

關鍵在於根節點的訪問時機：

走訪方式	順序	記憶口訣
前序 (Preorder)	根 ➡️ 左 ➡️ 右	根在前
中序 (Inorder)	左 ➡️ 根 ➡️ 右	根在中
後序 (Postorder)	左 ➡️ 右 ➡️ 根	根在後
層序 (Level-order)	逐層從左到右	BFS

走訪範例#

假設二元樹結構：

flowchart TB
    A((A)) --> B((B))
    A --> C((C))
    B --> D((D))
    B --> E((E))
    C --> F((F))
    C --> G((G))

走訪方式	結果	說明
前序	A ➡️ B ➡️ D ➡️ E ➡️ C ➡️ F ➡️ G	根 ➡️ 左 ➡️ 右
中序	D ➡️ B ➡️ E ➡️ A ➡️ F ➡️ C ➡️ G	左 ➡️ 根 ➡️ 右
後序	D ➡️ E ➡️ B ➡️ F ➡️ G ➡️ C ➡️ A	左 ➡️ 右 ➡️ 根
層序	A ➡️ B ➡️ C ➡️ D ➡️ E ➡️ F ➡️ G	逐層從左到右

BST 的中序走訪會產生有序序列，這是面試重要考點！

層序走訪實作 (BFS)#

使用 Batch Processing 技巧區分階層：

fun levelOrder(root: TreeNode?): List<List<Int>> {
    if (root == null) return emptyList()

    val result = mutableListOf<List<Int>>()
    val queue: ArrayDeque<TreeNode> = ArrayDeque()
    queue.add(root)

    while (queue.isNotEmpty()) {
        val levelSize = queue.size          // 鎖定當前層節點數
        val currentLevel = mutableListOf<Int>()

        repeat(levelSize) {
            val node = queue.removeFirst()
            currentLevel.add(node.value)
            node.left?.let { queue.add(it) }
            node.right?.let { queue.add(it) }
        }

        result.add(currentLevel)
    }

    return result
}

技巧：用 val levelSize = queue.size 在迴圈開始時鎖定當前層數量，避免使用特殊標記。

遞迴走訪模板#

前中後序遞迴程式碼

// 前序走訪
fun preorder(root: TreeNode?) {
    if (root == null) return
    println(root.value)      // 處理根
    preorder(root.left)      // 左子樹
    preorder(root.right)     // 右子樹
}

// 中序走訪
fun inorder(root: TreeNode?) {
    if (root == null) return
    inorder(root.left)       // 左子樹
    println(root.value)      // 處理根
    inorder(root.right)      // 右子樹
}

// 後序走訪
fun postorder(root: TreeNode?) {
    if (root == null) return
    postorder(root.left)     // 左子樹
    postorder(root.right)    // 右子樹
    println(root.value)      // 處理根
}

實務觀點：工作中較少區分前中後序，更常直接使用 DFS 或 BFS 的概念。學習這三種走訪主要是為了理解遞迴邏輯。