// 前序遍历：根 -> 左 -> 右 void preorder(TreeNode* root) { if (root == nullptr) return; cout val left); preorder(root->right); }

// 中序遍历：左 -> 根 -> 右 void inorder(TreeNode* root) { if (root == nullptr) return; inorder(root->left); cout val right); }

// 后序遍历：左 -> 右 -> 根 void postorder(TreeNode* root) { if (root == nullptr) return; postorder(root->left); postorder(root->right); cout val

每种遍历方式只是处理根节点的位置不同，其余结构一致。可根据需求选择合适顺序。

使用栈实现非递归DFS

递归本质是系统栈的调用，也可以手动用栈模拟，避免递归带来的栈溢出风险，尤其适用于深度较大的结构。

s.push(start);

while (!s.empty()) {
    int v = s.top();
    s.pop();

    if (!visited[v]) {
        cout << v << " ";
        visited[v] = true;
    }

    // 将所有未访问的邻接点压入栈（注意顺序可影响输出）
    for (auto it = g.adj[v].rbegin(); it != g.adj[v].rend(); ++it) {
        if (!visited[*it]) {
            s.push(*it);
        }
    }
}

使用栈时要注意：为了保证与递归顺序一致，通常需要逆序压入邻接点。因为栈是后进先出，先压入右边会导致左边先被访问。

基本上就这些。无论是图还是树，DFS的核心就是“一路走到底，走不通再回头”。递归写法简洁直观，适合大多数场景；非递归则更灵活可控。理解访问标记数组的作用和回溯时机是掌握DFS的关键。