二叉树的两种遍历

难度：T2

【知识点：树表示与遍历】

前置知识：二叉树、编号数组、孩子兄弟和递归遍历。

题目描述

给出一棵非空二叉树，结点身份编号1到n，指定根r。每个结点给出左、右孩子编号，0表示没有。按先根左后右得到前序，按先左后右最后根得到后序，输出两种序列。

输入格式

第一行n r；随后n行，第i行左孩子编号和右孩子编号。保证全部结点恰好构成题意所述合法树。

输出格式

两行，第一行前序，第二行后序，编号间以空格分隔。

样例输入

4 1
2 3
0 4
0 0
0 0

样例输出

1 2 4 3
4 2 3 1

样例解释

先访问1，再2及其右4，最后3；后序把每个根放在子树之后。

数据范围

1≤n≤20。普通结点编号在1..n，空孩子/兄弟记0。