GESP 六级 · GESP 202606 C++ 六级 第 24 题

使用栈非递归实现二叉树前序遍历时，若希望先访问左子树，通常应先将右孩子入栈，再将左孩子入栈。

递归问题关注两点：① 递归边界（终止条件）；② 递归关系（递推公式）。分析时展开前几步即可看出规律。

注意递归深度过大会导致栈溢出。递归必须包含终止条件，否则造成无限递归。

【考点】栈（STL stack）｜LIFO 特性与应用｜二叉树遍历非递归实现

🎯 考纲定位 本题考查 GESP 六级《C++ 程序设计》栈模块，命题人卡住的是"栈是后进先出"这一底层机制与遍历顺序的对应关系。绝大多数考生只背"前序=左根右"的结论，却不懂用栈模拟递归时入栈顺序的逆向逻辑，一遇到具体操作就凭直觉乱推。

🧠 解题思维 看到栈实现二叉树遍历，第一反应应是"栈是 LIFO，要后访问的节点先入栈"。前序顺序是根→左→右，根已访问，接下来要访问左孩子。若栈中同时存在左右孩子，必须让左孩子先出栈，因此右孩子要后入栈。本质是：栈的进栈顺序永远与期望的出栈顺序完全相反。这一规律可迁移到后序、层序等所有栈应用题。

🪤 陷阱拆解 错误选项若存在，必是"先左后右入栈"，利用考生"前序先左→那就先左入栈"的直觉陷阱。命题人故意把"访问顺序"与"入栈顺序"混为一谈，让你忽略栈的后进先出本质。边界上，当节点无左孩子时，只右孩子入栈，出栈顺序自然正确，这容易让人误以为入栈顺序可随意。

🔄 反命题思维 如果把题目改成"中序非递归实现，应先访问左子树，入栈顺序如何？"答案就变成"左孩子先入栈"——因为中序是左→根→右，栈里需要左先出。刷到栈相关遍历题，先问自己：期望的出栈顺序是什么，入栈顺序必须与之相反。