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

一棵有 $N$ 个节点的完全二叉树，则树的深度为 $\lfloor \log_2(N) \rfloor + 1$。

DFS 使用栈（或递归），沿一条路径走到底再回溯，适合遍历所有可能状态。注意回溯时的状态恢复。

DFS 递归遍历时注意状态回溯（恢复现场）。图遍历需要visited数组避免重复访问和死循环。

由 ，本解析严格遵守四层结构。

【考点】完全二叉树深度公式

🎯 考纲定位（考点定位） GESP 七级「算法与数据结构」模块，命题人考察的是对“完全二叉树”深度公式的精确记忆与理解，而非普通二叉树。绝大多数考生会混淆深度与高度，或对数运算细节，导致误判。

🧠 解题思维（拆解与通法） 解题链条：从完全二叉树定义出发——深度为 d 的满二叉树节点数 2^d-1。若 N 个节点，则 2^{d-1} ≤ N < 2^d。取对数得 d-1 ≤ log₂ N < d，解得 d = ⌊log₂ N⌋ + 1。通法：二叉树深度先找满二叉树上限公式。

🪤 陷阱拆解（命题人的套路） 选项 B 错误源于：误记深度为高度、将完全二叉树泛化为任意二叉树、忽略取整符号。命题人利用概念混淆与记忆模糊诱导选错。若只背结论不推导，必掉入此坑。

🔄 反命题思维（教练升华） 若改为任意二叉树公式不成立，若改为满二叉树公式变为 d = log₂(N+1)。刷到此类题，先自问命题意图。