1296 - 二叉树的后序遍历
描述

后序遍历输出此二叉树每个节点的编号,每行输出一个编号。

后序遍历(LRD),是二叉树遍历的一种,也叫做后根遍历、后序遍历、后序周游,可记做左右根。后序遍历首先遍历左子树,然后遍历右子树。最后访问根节点


输入

输入一个整数n(n <= 100000),表示二叉树中节点个数,编号为1~n。然后输入n-1行(树的n-1条边),每行包括两个整数,第i行两个整数(u,v),v表示u的儿子节点,第一次加入为左节点,第二次表示右节点。

输出

后序遍历的顺序,中间用空格隔开


样例

输入

10
2 8
2 4
8 10
8 7
4 3
10 9
7 5
3 1
3 6

输出

9 10 5 7 8 1 6 3 4 2
提示

根据约定,第一个加入的点是左儿子,第二个是右儿子,所以得到的树如上图所示

fdk7sx2l.png

题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 74
通过次数 69