CJDF02｜树的先序访问 题解

核心算法

建立无向图后将每个结点的邻接点排序，从结点 1 开始 DFS。

思路推导

先记录当前结点，再按编号递增访问它的孩子。树没有环，递归参数保留父结点即可避免立刻走回去。

正确性说明

对任一结点，算法在进入时输出它，并按从小到大的顺序完整递归访问各个非父相邻结点。因此每个结点恰好输出一次，且顺序满足题意。

复杂度

排序总复杂度不超过 $O(n\log n)$，DFS 为 $O(n)$；空间复杂度 $O(n)$。

易错点

• 无向边要双向加入；
• 邻接点必须排序，不能依赖输入顺序；
• 输出结点的时机是“刚进入结点时”。