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

以下代码实现了二叉树的深度优先搜索（DFS），并统计叶子结点的数量，则横线上应填写（ ）。

int countLeafNodes(TreeNode* root) {
    if (root == nullptr) return 0;

    stack<TreeNode*> s;
    s.push(root);
    int count = 0;
    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();

        if (node->left == nullptr && node->right == nullptr) {
            count++;
        }

        if (node->right) s.push(node->right);
        ________________________ // 在此处填入代码
    }
    return count;
}

位运算：&（与）、|（或）、^（异或）、~（取反）、<<（左移）、>>（右移）。异或性质：a^a=0，a^0=a。

区分逻辑运算(&&,||,!)和位运算(&,|,~,!)。左移右移注意符号位的处理（算术右移vs逻辑右移）。负数的位运算要小心。

【考点】深度优先搜索（DFS）｜栈操作｜树遍历

🎯 考纲定位 GESP 六级《树与图》模块，DFS 遍历与栈操作的结合考查。命题人专盯"栈与队列混用"的盲点：学生背了"前序遍历先左后右"的口诀，却忘了栈是 LIFO，入栈顺序直接决定访问次序。此题在六级树遍历章节属于高频考点，往往作为选择题出现，测试学生对栈操作细节的掌握。若学生误以为栈操作可省略，或混淆栈与队列，就会漏掉左子树，导致统计错误。

🧠 解题思维 看到 DFS 用栈，第一反应是"后进先出"。程序已在 push(root) 后循环弹出，紧接着判断叶子并累加 count。若按"先右后左"入栈，弹出顺序才是"先左后右"，符合二叉树的前序遍历逻辑。但本题只求叶子数，顺序不影响结果，关键是要把左子树也压入栈，否则左子树永远无法被访问，count 会少。注意：栈中若漏掉左子树，后续循环会继续弹出右子树，但左子树永远不会被处理，导致统计不全。因此，补全左子树入栈是确保所有节点都被遍历的必要条件。

🪤 陷阱拆解 A 项 if (node->left) s.push(node->left); 语法正确，补全左子树入栈，符合 LIFO 特性。B 项 s.pop(node->left) 无 pop 重载且参数类型错误，C 项 s.front(node->left) 不存在 front 方法，D 项重复 push(node->right) 会导致右子树被压两次，栈内出现重复节点，严重破坏遍历逻辑。命题人故意把"栈操作"和"队列操作"混在一起，诱导学生误选 C 或 D。

🔄 反命题思维 若改成 BFS 遍历，栈要换成队列，入队顺序改为"先左后右"。若题目改为统计内部节点数，只需把判断条件从"左右均为空"改为"至少有一个子节点"。刷到类似题先问：这里用栈还是用队列？遍历顺序是否影响结果？