题目描述：

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

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

请你编写程序，读入树的结构并输出这棵树的先序遍历。

输入：

输入包含三部分：

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 的父节点，其中 father[1] = 0，表示 1 号节点为根节点。

输出：

输出树的先序遍历序列。

输入样例 1：

5
1
1 2
1 3
2 4
2 5

输出样例 1：

1 2 4 5 3

输入样例 2：

5
2
0 1 1 2 2

输出样例 2：

1 2 4 5 3

数据范围：

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

---

题解思路：

问题要求：根据输入的树的结构，输出树的先序遍历。

树的先序遍历是一种递归遍历方式，首先访问根节点，然后依次访问每个子节点的子树。先序遍历的顺序为：根节点 -> 左子树 -> 右子树。

解决方法：

我们根据输入的类型设计两种不同的输入方式，然后统一转换成邻接表形式进行处理。接着，利用深度优先搜索（DFS）算法来实现树的先序遍历。接下来我们讲解邻接表的结构、原理及存储方式。

综上，我们完成这个题需要明确两大知识点：存储结构以及读入方式。 接下来依次介绍这两个知识点。

---

一.存储结构：邻接表的结构、原理及存储方式

在图论和树的相关问题中，邻接表（Adjacency List）是一种常用的数据结构，用来高效地存储图或树中的边。相较于邻接矩阵，邻接表在处理稀疏图（边数较少的图）时非常节省空间。

原理：

• 邻接表的基本思想是：每个节点保存与它相邻的所有节点的列表。
• 每个节点对应一个列表，列表中存储所有与该节点直接相连的其他节点。

例如，对于一棵树（或图）中的一条边 u - v，在邻接表中，节点 u 的邻接列表中存储节点 v，同时节点 v 的邻接列表中也存储节点 u。对于树结构，只需要存储单向边（子节点指向父节点或父节点指向子节点）。

数据结构形式：

• 如果我们有 n 个节点，那么可以使用一个大小为 n 的数组或 n 个链表，其中每个元素存储与该节点相邻的节点集合。

以树为例的邻接表结构：

假设树的边为：

1 - 2
1 - 3
2 - 4
2 - 5

邻接表存储如下：

1 -> [2, 3]
2 -> [1, 4, 5]
3 -> [1]
4 -> [2]
5 -> [2]

在这种结构下，我们可以很方便地通过遍历某个节点的邻接列表来访问与之相邻的所有节点。

二.笔试中常见的树的读入方式:

1.通过边的形式读入树结构

在方式 1 中，树的输入是以 n-1 条边的形式给出的，这种表示方式一定要注意确定树的方向性。

• 1.在输入中，树是无向边的形式(例如树是从1到2的有向边，但是读入可能会读入2 1 这种边的关系)，所以在遍历时我们要转换为有向的结构。即，当你从父节点访问某个子节点后，不应该回到父节点。为此，你需要在DFS的时候消除返祖边
• 具体实现上，你可以在dfs的时候额外加一个参数:father,当要访问的下一个节点 == father 时，不返祖递归。否则这样会进入DFS死循环

2.通过father数组形式读入树结构

方式 1 是通过 无向图 的形式读取树的边，然后我们需要将其处理成树的形式。而 方式 2 更加贴近树的有向图结构，father 数组直接表示了树的父子关系，因此我们不需要处理双向边。构建邻接表的过程如下：

• 对于每一个节点 i，father[i] 是它的父节点，也就是存在一条边father[i] i。因此我们给tree[father[i]] 加入新的节点 i 即可。

三.代码实现

一. C++ 实现

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> tree;  // 邻接表表示树
vector<int> preorder_result;  // 存储先序遍历结果

// DFS 先序遍历
void dfs(int node, int parent) {
    preorder_result.push_back(node);  // 访问当前节点
    for (int child : tree[node]) {
        if (child != parent) {  // 避免回到父节点
            dfs(child, node);  // 递归访问子节点
        }
    }
}

int main() {
    int n, type;
    cin >> n >> type;

    tree.resize(n + 1);  // 邻接表大小为 n + 1，节点编号从 1 开始

    if (type == 1) {
        // 方式一：通过边的形式输入
        for (int i = 0; i < n - 1; ++i) {
            int u, v;
            cin >> u >> v;
            tree[u].push_back(v);
            tree[v].push_back(u);  // 无向图，双向存储
        }
    } else if (type == 2) {
        // 方式二：通过 father 数组输入
        vector<int> father(n + 1);
        for (int i = 1; i <= n; ++i) {
            cin >> father[i];
            if (father[i] != 0) {
                tree[father[i]].push_back(i);  // father[i] 是 i 的父节点
            }
        }
    }

    // 从根节点 1 开始 DFS 进行先序遍历
    dfs(1, -1);

    // 输出先序遍历结果
    for (int node : preorder_result) {
        cout << node << " ";
    }
    cout << endl;

    return 0;
}

二. Python 实现

from sys import stdin, setrecursionlimit
from collections import defaultdict

setrecursionlimit(10**6)  # 增加递归深度限制

# DFS 先序遍历
def dfs(node, parent):
    preorder_result.append(node)
    for child in tree[node]:
        if child != parent:
            dfs(child, node)

# 读取输入
n = int(input())
tree = defaultdict(list)  # 邻接表

type = int(input())

if type == 1:
    # 方式一：通过边输入
    for _ in range(n - 1):
        u, v = map(int, input().split())
        tree[u].append(v)
        tree[v].append(u)
else:
    # 方式二：通过 father 数组输入
    father = list(map(int, input().split()))
    for i in range(1, n + 1):
        if father[i - 1] != 0:
            tree[father[i - 1]].append(i)

preorder_result = []
dfs(1, -1)

# 输出先序遍历结果
print(' '.join(map(str, preorder_result)))

三. Java 实现

import java.util.*;

public class Main {
    static List<List<Integer>> tree = new ArrayList<>();
    static List<Integer> preorder_result = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int type = sc.nextInt();

        // 初始化邻接表
        for (int i = 0; i <= n; i++) {
            tree.add(new ArrayList<>());
        }

        if (type == 1) {
            // 方式一：通过边输入
            for (int i = 0; i < n - 1; i++) {
                int u = sc.nextInt();
                int v = sc.nextInt();
                tree.get(u).add(v);
                tree.get(v).add(u);
            }
        } else {
            // 方式二：通过 father 数组输入
            for (int i = 1; i <= n; i++) {
                int father = sc.nextInt();
                if (father != 0) {
                    tree.get(father).add(i);
                }
            }
        }

        // 从根节点 1 开始 DFS 进行先序遍历
        dfs(1, -1);

        // 输出先序遍历结果
        for (int node : preorder_result) {
            System.out.print(node + " ");
        }
        System.out.println();
    }

    // DFS 先序遍历
    static void dfs(int node, int parent) {
        preorder_result.add(node);  // 访问当前节点
        for (int child : tree.get(node)) {
            if (child != parent) {
                dfs(child, node);
            }
        }
    }
}