GESP 七级 · GESP 202506 C++ 七级 第 5 题

假定只有一个根节点的树的深度为 1，则一棵有 $ N $ 个节点的完全二叉树，则树的深度为（ ）。

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

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

【考点】GESP 七级算法：对数运算｜完全二叉树性质｜深度定义陷阱

这题考的是完全二叉树深度公式的直接应用，属于 GESP 七级 C++ 算法模块中"树与二叉树"的必考题型。命题人专门设计这个公式题，就是筛掉那些只背模板、不读定义的考生。

解题链很简单：深度定义是根深度=1 时树有几层。完全二叉树深度 d 满足 2^{d-1} ≤ N < 2^d，反推得 d = floor(log2(N)) + 1。选项 A 正是此式。B 项少 1，源于把根深度记成 0 的误区；C 项用 ceil 是因为混淆"节点数"与"层数"概念；D 项是纯误导，完全二叉树深度公式在给定 N 下唯一确定。

陷阱最阴险处在于定义偷换：题干明确"根节点深度为 1"，但 C++ 数组下标从 0 起，编程时若按 0 基数深度写公式就自然掉进 B 项坑。记住：公式本身没错，错的是把 0 基数和 1 基数混用。

反命题：若改题设"根深度为 0"，答案变 B；若改"非完全二叉树"，则 D 成立。教练提醒：每次遇到树深度题，先确认根节点深度定义和树类型，别死记公式。