GESP 八级 · GESP 202503 C++ 八级 第 7 题

$N$ 个节点的平衡二叉树的高为（ ）。

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

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

【考点】平衡二叉树性质｜二叉树高度定义｜最坏最好情况

🎯 考纲定位：本题出自《GESP 考试大纲》算法与数据结构模块（八级）“树与二叉树”部分。命题人卡住的是考生对"平衡二叉树高度范围"的模糊认知——绝大多数人误以为高度由节点数唯一确定，实则平衡二叉树允许不同结构对应不同高度。

🧠 解题思维：看到"平衡二叉树"先想高度定义：空树高度0，单节点高度1。平衡约束为左右子树高度差≤1。N个节点能构造的最小高度是⌊log₂N⌋+1（完全二叉树），最大高度是⌊log₂N⌋+2（如根左右子树高度差1且尽可能高）。N=3可构造高度2或3；N=4可构造高度2或3；N=5最小高度3，最大高度4。因此高度不是N的函数，而是区间，无法用单一公式表示。

🪤 陷阱拆解：A项⌊log₂N⌋低估了（最小高度比它大1）；B项⌈log₂N⌉是最好情况，但存在更高层的平衡二叉树；C项⌊log₂N⌋+1是下限，却当成唯一解；D项"无法确定"正确。命题人利用考生对"平衡二叉树=完全二叉树"的刻板印象，以及"高度=⌊log₂N⌋+1"的机械记忆，故意设置绝对化表述选项。

🔄 反命题思维：若改为"N个节点的平衡二叉树的最小高度为（ ）"，答案即C；若问"最大高度"，答案是⌊log₂N⌋+2。刷到类似题，先问"高度是否唯一？"而不是直接套公式。