二叉树的前序遍历(Preorder Traversal)

题目描述

二叉树有三种最基本的遍历方式，前序遍历的访问顺序是：

根节点 → 左子树 → 右子树

也就是：每当来到一个节点，先访问（输出）它自己，再递归遍历它的左子树，最后递归遍历它的右子树。

现在给你一棵二叉树，请你输出它的前序遍历序列。

输入格式

第一行一个整数 n，表示二叉树的节点个数，节点编号为 1 ~ n，其中 1 号节点是根节点。

接下来 n 行，第 i 行两个整数 l 和 r，分别表示编号为 i 的节点的左孩子和右孩子的编号。如果没有左孩子（或右孩子），对应位置为 0。

输出格式

输出一行，包含 n 个整数，表示前序遍历的节点编号，相邻两个数之间用一个空格隔开。

样例输入

7
2 3
4 5
0 0
6 7
0 0
0 0
0 0

样例输出

1 2 4 6 7 5 3

数据范围

• 1 ≤ n ≤ 1000
• 输入保证构成一棵以 1 为根的合法二叉树

提示

用递归写遍历非常简单，前序遍历的框架是：

dfs(节点 u):
    如果 u == 0: 返回
    输出 u          // 前序：先处理根
    dfs(左孩子)
    dfs(右孩子)

这个序列也叫树的 DFS 序：沿着深度优先搜索访问节点的顺序。