GESP 六级 · GESP 六级样题（C++ 组） 第 22 题

深度优先遍历算法的时间复杂度为 $O(N log N)$，其中 $N$ 为树的节点数。（ ）

这题考的是遍历复杂度，别被'log'带偏。树遍历本质是访问每个点一次、每条边一次，总数固定为O(N)。

很多考生看到'二叉树''log'就条件反射选O(N log N)，其实是混淆了'遍历'和'查找/排序'。遍历只是扫一遍，不会重复访问；只有带比较、调整或平衡的操作才会引入对数因子。

【考点】深度优先遍历｜树遍历复杂度｜时间复杂度分析

1. 考纲定位

GESP C++ 组六级，属于'基础编程'模块中'树的基本算法'子考点。命题人专门挑这个点，是因为六级考生普遍会背'遍历是 O(N)'，但很少能准确区分'树的遍历'与'图遍历'或'排序'的复杂度差异——这道题就是用 O(N log N) 这个看似合理实则错误的选项，卡住那些只记结论不推过程的考生。