GESP 七级 · GESP 202409 C++ 七级 第 21 题

一颗 $N$ 层的完全二叉树，一定有 $2^N - 1$ 个结点。

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

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

【考点】完全二叉树｜结点数｜满二叉树

🎯 考纲定位（考点定位） 本题考查《GESP 大纲》“数据结构与算法”模块中“二叉树”相关知识点。命题人故意用“完全二叉树”偷换“满二叉树”概念，卡住考生对“层满”与“左满”的区分能力。

🧠 解题思维（拆解与通法） 看到题先想：N层二叉树有多少节点？关键观察：完全二叉树定义——除最后一层外，其余各层都满，且最后一层节点靠左。推理依据：前N-1层节点数固定为 $2^{N-1}-1$，第N层节点数只能在 $1 \sim 2^{N-1}$ 之间。通法：判断是否为完全二叉树，先算深度N，再验证前N-1层节点总数是否等于 $2^{N-1}-1$，最后看第N层节点数是否落在合法区间。

🪤 陷阱拆解（命题人的套路） 错误选项B（错误）的设计逻辑：命题人利用"完全"与"满"的语义混淆，把"一定有 $2^N - 1$ 个结点"这一绝对化结论强加给完全二叉树。最阴险的细节在于"一定有"——这暗示了所有N层完全二叉树节点数相同，完全不符合定义。如果你只背"完全二叉树节点数= $2^N - 1$"这种结论、不理解本质，就会掉进这个陷阱。

🔄 反命题思维（教练升华） 命题人若改条件，比如把"完全二叉树"换成"满二叉树"，答案就变成A；或者问"N层完全二叉树最多有多少节点"，答案就是 $2^N - 1$。刷到类似题时，先问自己"命题人想考我什么"——是考定义、考计数、还是考陷阱？