GESP 八级 · GESP 202409 C++ 八级 第 5 题

$n$ 个结点的二叉树，执行释放全部结点操作的时间复杂度是（ ）。

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】二叉树遍历｜时间复杂度分析｜数据结构基础

🎯 考纲定位：本题考查《GESP 考试大纲》八级"数据结构"模块中"二叉树"相关知识点。命题人用"释放全部结点"这一操作卡住考生对遍历算法基础的掌握——很多人误以为二叉树操作必含递归开销，却忽略了释放每个结点只需访问一次。

🧠 解题思维：看到"释放全部结点"，先想：释放一个结点需要做什么？ 访问一次该结点（读取数据、断开父指针、调用 free），耗时 O(1)。再想：访问多少个结点？ 二叉树有 n 个结点，释放全部必然访问 n 次。总时间 = n × O(1) = O(n)。通法：任何"遍历并处理每个元素"的操作，只要处理单个元素是 O(1)，整体复杂度就是 O(n)——这是线性遍历的标志性特征。

🪤 陷阱拆解：选项 B 用 n log n 混淆排序复杂度，选项 C 用 log n 偷换"树高"概念，选项 D 用 2^n 把"结点总数"当"高度"。最阴险的是"释放全部结点"这个绝对化表述——不遍历无法释放，但遍历复杂度与树高无关，只与结点数相关。如果你只背结论"二叉树操作 O(log n)"，就会误选 C。

🔄 反命题思维：站在命题人视角：若把"释放全部结点"改成"释放所有深度为 k 的结点"，复杂度变为 O(n × k)；若改成"按层序释放"，仍是 O(n)。刷到类似题时，先问自己"命题人想考我什么"——这里显然是考线性遍历的本质，而非树高或排序。