【深度优先搜索1】树的存储和遍历

深度优先搜索(Depth First Search , DFS)是一种用于遍历或搜索图（图可以是树、无向图、有向图等）的算法。它按照深度优先的策略，优先访问当前节点的下一层邻接节点，直到无法继续为止，再回溯到上一层。

你可以先粗略的理解为：DFS就是在图上做特定的递归，$DFS \subset 递归$

前言:通过【图论的存储】图的存储，我们已经学会怎么把图存进邻接表且怎么遍历。由于树是有向无环图，所以树的存储和遍历和图基本是一致的。而本节课主要是让大家熟悉在笔试中1.树的两种读入方式以及2.树的先序遍历。

第一种读入形式:边形式

题目描述：

给定一棵 n 个节点的树，节点编号为$1-n$，树的根节点固定为 1。我们有两种方式表示树的结构：

1. 方式一：通过 n-1 条边的形式，每条边 u v 表示节点 u 和节点 v 之间存在一条边。
2. 方式二：通过一个 father 数组，father[i] 表示节点 i+1 的父节点。

请你编写程序，读入树的结构并使用深度优先搜索遍历打印这棵树的节点编号。

为了输出统一，从根节点开始遍历，优先访问序号小的子节点。

输入：

输入包含三部分：

1. 第一行包含一个整数 n，表示树的节点个数。
2. 第二行包含一个整数 type，表示树的表示方式：
   • 如果 type = 1，表示通过边的形式输入。
   • 如果 type = 2，表示通过 father 数组输入。
3. 如果 type = 1，接下来会有 n-1 行，每行两个整数 u v，表示树中节点 u 和节点 v 之间存在一条边。
4. 如果 type = 2，接下来一行有 n 个整数，father[i] 表示节点 i+1 的父节点，其中 father[0] = 0，表示 1 号节点为根节点,没有父节点。

输出：

打印遍历这棵树的节点编号。

输入样例 1：

5
1
1 2
1 3
2 4
2 5

输出样例 1：

1 2 4 5 3

样例1图例：

      1
     / \
    2   3
   / \
  4   5

输入样例 2：

5
2
0 1 1 2 2

输出样例 2：

1 2 4 5 3

数据范围：

• $1 \leq n \leq 10^5$