GESP 六级 · GESP 202503 C++ 六级 第 19 题

以下代码实现的是二叉树的中序遍历：

void traverse(TreeNode* root) {
    if (root == nullptr) return;
    traverse(root->left);
    cout << root->val << " ";
    traverse(root->right);
}

根据二叉树的遍历特性，先/前序遍历确定根节点，中序遍历确定左右子树范围，从而重构整棵树，再输出后序遍历结果。

易混淆三种遍历的顺序。先序：根左右；中序：左根右；后序：左右根。注意遍历结果中相邻节点的关系。

【考点】二叉树遍历｜递归逻辑｜中序遍历

【考纲定位】本题考查《GESP 六级 数据结构与算法》模块核心考点“二叉树遍历”，命题人专卡递归逻辑顺序。绝大多数考生能写出中序遍历代码，但容易混淆“先序/中序/后序”的递归调用次序，此题用“代码正确性判断”替代“手写遍历”，精准考察对递归栈执行顺序的理解深度。

【解题思维】 1. 看到递归函数先定位到“遍历”关键词，立刻联想二叉树三种遍历顺序。 2. 逐行拆解代码： - if (root == nullptr) return;：处理空节点边界条件，递归终止。 - traverse(root->left);：递归先处理左子树。 - cout << root->val << " ";：当前节点输出。 - traverse(root->right);：递归后处理右子树。 3. 对照中序遍历定义：左→根→右，代码顺序完全匹配。 4. 通法提炼：判断递归遍历代码正确性，只需核对“递归调用次序”与“输出位置”是否对应三种遍历的定义顺序。

【陷阱拆解】 1. 选项 B 错误陷阱：若将 cout 移到第一个 traverse 之后，则变为后序遍历；移到第二个 traverse 之后，则变为前序遍历。命题人利用“输出位置决定遍历名称”这一易混淆点。 2. 边界条件陷阱：若省略 if (root == nullptr) return;，递归将陷入死循环（访问空指针），这是 C++ 指针操作的经典错误。 3. 语义陷阱：题目问“代码实现的是二叉树的中序遍历”，考生易忽略“中序”仅指“左-根-右”顺序，而误以为只要遍历树就行。此题实则考“顺序匹配”，非“是否遍历”。 4. 若只背结论不理解本质，看到 traverse(root->left); 就以为“先左”，却不知递归调用栈中左右子树的执行顺序完全由代码顺序决定。

【反命题思维】 若将 traverse(root->left) 与 traverse(root->right) 顺序互换，代码变为前序遍历；若将 cout 移至递归调用之后，则变为后序遍历。若添加条件 if (root->val > 0) 再输出，则遍历结果因节点值而异。命题人常通过“微调调用顺序”或“增加判断条件”来生成同类题，刷到此类题先问自己：“想考我记顺序还是理解递归？”