樹結構前序/後序遍歷順序原理解析

前序遍歷

順序：根 → 左子樹 → 右子樹

1. 訪問當前根節點。
2. 遞歸前序遍歷左子樹（將左子節點視為新根，重複步驟 1-2）。
3. 左子樹耗盡後，遞歸前序遍歷右子樹。

本質是深度優先搜索 (DFS)，優先往深處走，走不下去再回溯處理右兄弟。

後序遍歷

順序：左子樹 → 右子樹 → 根

1. 遞歸後序遍歷左子樹。
2. 遞歸後序遍歷右子樹。
3. 訪問當前根節點。

根節點最後處理，適合「先處理孩子再處理父親」場景（如釋放記憶體、計算目錄大小）。

中序遍歷（補充）

左子樹 → 根 → 右子樹。二叉搜索樹中序遍歷得遞增序列。

記憶口訣

• 前序：根左右（根在前）
• 中序：左根右（根在中）
• 後序：左右根（根在後）

遞歸代碼範例

void preOrder(TreeNode root) {
    if (root == null) return;
    visit(root);           // 根
    preOrder(root.left);   // 左
    preOrder(root.right);  // 右
}

void postOrder(TreeNode root) {
    if (root == null) return;
    postOrder(root.left);  // 左
    postOrder(root.right); // 右
    visit(root);           // 根
}