GESP 六级 · GESP202609 C++ 六级 第 9 题

以下代码实现二叉树左子树优先的深度优先搜索算法，则横线上应填写（　　）。

void dfs(TreeNode *root) {
if (root == nullptr)
return;
stack<TreeNode *> s;
s.push(root);
while (!s.empty()) {
TreeNode *node = s.top();
s.pop();
cout << node->value << " ";

———————————————————————— // 在此处填入代码

}
}

A.

s.push(node->right);
s.push(node->left);

B.

s.push(node->left);
s.push(node->right);

C.

if (node->right)
s.push(node->right);
if (node->left)
s.push(node->left);

D.

if (node->left)
s.push(node->left);
if (node->right)
s.push(node->right);

栈是后进先出结构，要访问左子树先，必须让右子树先入栈。代码里先压右再压左，循环里就会先弹出左子树。但节点可能没有左右孩子，直接 s.push(nullptr) 会导致后续访问 node->value 崩溃，所以必须用 if 判空。

A、B 没判空会崩溃；D 顺序反了变成右优先；只有 C 既判空又先压右。

1. 考纲定位

本题考查《GESP 考试大纲》六级"数据结构与算法"模块中的二叉树遍历与栈的应用。命题人卡住的是考生对栈 LIFO 特性的理解——知道要左优先，却忘了栈是后进先出，所以必须先压右再压左；同时忽略了判空，这是六级题典型的"双陷阱"设计。

2. 解题思维

看到"左子树优先"立刻想到：栈里最后压的会最先弹出，所以右子树必须比左子树先压栈。遍历顺序是：根→左→右，因此压栈顺序必须是：右→左。再看代码结构，while 循环里已经 pop 了当前节点并输出，接下来要压孩子节点。但孩子可能不存在，直接压 nullptr 会导致后续访问 node->value 崩溃，所以必须用 if 判空。