求Euler Tour Tree遍历结果数组大小为2N-1的证明思路

嘿，这个问题其实很好理解，我给你拆解两种直观的证明思路，帮你搞明白为啥任意N节点树的欧拉游遍历结果数组大小恰好是2N-1。

方法一：数学归纳法 #

这是最经典的证明方式，一步步推导很清晰：

• 基础情况：当树只有1个节点（N=1）时，欧拉游的结果就是这个节点本身，数组大小为1，而2×1-1=1，完全符合结论。
• 归纳假设：假设对于所有节点数为k的树，其欧拉游数组的大小都是2k-1。
• 归纳步骤：现在看节点数为k+1的树——树是连通无环的，所以必然存在至少一个叶子节点（度数为1的节点）。我们把这个叶子节点从树上移除，剩下的就是一个k节点的树，根据归纳假设，它的欧拉游数组大小是2k-1。
  现在把叶子节点加回去：它会和原树中的某个节点（父节点）相连。在欧拉游遍历中，当我们走到父节点时，会先进入叶子节点（记录一次叶子），然后回溯回父节点（再记录一次父节点）。这相当于在原来的数组里额外添加了2个元素，数组大小变为(2k-1)+2=2(k+1)-1，正好符合结论。

方法二：基于边与移动次数的计数 #

这个思路更直观，从树的基本性质出发：

• 首先，树的核心性质是：N个节点的树恰好有N-1条边（连通无环图的边数公式）。
• 欧拉游的本质是深度优先遍历的完整路径：每一条边都会被遍历两次——一次是从父节点走向子节点（向下遍历），一次是从子节点回溯回父节点（向上返回）。所以总共有2×(N-1)次移动。
• 而欧拉游的数组大小等于移动次数+1：因为数组的第一个元素是初始节点（根节点），每移动一次就会记录下到达的节点。比如1个节点时，移动0次，数组大小0+1=1；2个节点时，移动2次（根→叶子→根），数组大小2+1=3。
• 代入计算：2×(N-1)+1=2N-2+1=2N-1，完美匹配结论。

简单来说，要么用归纳法从最小的树逐步推导，要么从树的边数和遍历的移动逻辑入手，都能轻松证明这个结论~

内容的提问来源于stack exchange，提问作者Игорь Тарлинский