GESP 六级 · GESP 202406 C++ 六级 第 14 题

同上题中的二叉树，阅读以下二叉树的深度优先搜索代码:

#include <iostream>
#include <stack>

using namespace std;

// 非递归深度优先搜索（DFS）
TreeNode* dfs(TreeNode* root, int a) {
    if (root == nullptr) return nullptr;

    stack<TreeNode*> stk;
    stk.push(root);

    while (!stk.empty()) {
        TreeNode* node = stk.top();
        stk.pop();
        if (node->val == a)
            return node;

        cout << node->val << " "; // 访问当前节点

        if (node->right) stk.push(node->right); // 先压入右子节点
        if (node->left) stk.push(node->left); // 再压入左子节点
    }
    return nullptr;
}

使用以上算法，在二叉树搜索数值 $20$ 时，可能的输出是（ ）。

排列组合问题：先判断是否考虑顺序（排列P vs 组合C），再确定是否允许重复。乘法原理分步，加法原理分类。

区分排列（考虑顺序，$P(n,m)$）和组合（不考虑顺序，$C(n,m)$）。注意特殊元素优先处理、正难则反等计数技巧。

【考点】先序遍历｜栈的应用（非递归 DFS）

1. 🎯 考纲定位 本题考查《GESP 六级 C++ 大纲》中"数据结构与算法"模块的二叉树遍历与栈的应用。命题人刻意设置"非递归"实现，就是要卡住那些只会背"先序遍历是根左右"结论、却完全不理解栈的 LIFO 特性如何决定遍历顺序的考生——他们看到"输出顺序"就断定是标准先序，却忽略了压栈顺序对遍历序列的具体影响。

2. 🧠 解题思维 看到非递归 DFS 代码，第一步必须分析压栈顺序：先压 right 再压 left，意味着弹出时左子节点先被访问，整体仍是先序（根-左-右）。搜索 20 时，若树中存在 20 则找到即返回、输出截断；若不存在则遍历整棵树输出完整先序序列。解题关键：还原"同上题中的二叉树"结构——根据选项反推，根为 5，左子 2，2 的左子 -4，-4 的右子 3，3 的右子 17，17 的左子 9，其先序遍历恰好为 5 2 -4 3 17 9，与选项 A 完全匹配。

3. 🪤 陷阱拆解

• 选项 B：数值顺序完全打乱，属于混淆先序与后序/中序的干扰项；
• 选项 C：把 17 提前到 -4 之前，看似合理实则违背压栈逻辑——由于右子节点先入栈，只有当左子树完全遍历后才会访问右子节点，因此 17 不可能在 -4 之前被输出；
• 最阴险细节：代码中的提前返回 if (node->val == a) return node;。若 20 存在于树中（比如是 -4 的左子），输出会在访问 20 时截断，但题目问的是"可能的输出"，暗示 20 不在树中，因此输出完整先序序列。很多考生只背"先序遍历"结论，却忽略压栈顺序对遍历序列的具体影响，从而误选 C。

4. 🔄 反命题思维 若将压栈顺序改为先左后右，遍历序列会变成 5 2 -4 3 17 9 的反序（根-右-左），答案将完全不同；若去掉提前返回语句，即使 20 在树中，输出也会包含后续节点，导致选项 A 不再成立。这提醒我们：任何对实现细节的微小改动都可能彻底改变结果。刷到类似题时，先问自己：压栈顺序是什么？提前返回是否影响输出？树的结构能否由选项反推？