题目描述

在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（ left subtree ）和“右子树”（ right subtree ）。如下图，每个节点有一个编号。树的访问方式叫做中序遍历，方法为：首先中序遍历左（右）子树，再访问根，最后中序遍历右（左）子树。如下图，中序遍历为：4、3、7、1、6、2、5、8。现在输入一棵二叉树（ 1 为根节点），请你输出二叉树的中序遍历。

输入格式

第一行一个整数 $n$ 代表二叉树节点个数（ $n \lt 20$ ）。

第 2 ~ n+1 行，每行三个整数，第一个整数代表第 i 个节点的编号，第二个整数左儿子的编号，第三个整数为右儿子的编号，如果没有左或者右儿子则为 0 。

输出格式

依次输出二叉树中序遍历节点

样例

8
1 3 5
2 0 0
3 4 7
4 0 0
5 6 8
6 0 2
7 0 0
8 0 0

4 3 7 1 6 2 5 8