【模板】二叉树的遍历
时间限制:C/C++/Rust/Pascal 5秒,其他语言10秒
空间限制:C/C++/Rust/Pascal 512 M,其他语言1024 M
64bit IO Format: %lld

题目描述

\hspace{15pt}对于给定的二叉树,你需要维护:
{\hspace{20pt}}_\texttt{1.}\,二叉树的先序遍历;
{\hspace{20pt}}_\texttt{2.}\,二叉树的中序遍历;
{\hspace{20pt}}_\texttt{3.}\,二叉树的后序遍历;
{\hspace{20pt}}_\texttt{4.}\,二叉树的层序遍历。

输入描述:

\hspace{15pt}第一行输入一个整数 n\left(1\leqq n\leqq 5 \times 10^5\right) 代表二叉树的节点数量。
\hspace{15pt}此后 n-1 行,每行输入三个整数 u, v, op \left(1\leqq u, v\leqq n; 0 \leqq op \leqq 1 \right) 代表当前节点 u 的父节点为 v ,其中 op = 0 代表当前节点是父节点的左儿子,op = 1 代表当前节点是父节点的右儿子。

输出描述:

\hspace{15pt}在第一行上输出 n 个整数,代表二叉树的先序遍历;
\hspace{15pt}在第二行上输出 n 个整数,代表二叉树的中序遍历;
\hspace{15pt}在第三行上输出 n 个整数,代表二叉树的后序遍历;
\hspace{15pt}在第四行上输出 n 个整数,代表二叉树的层序遍历。
示例1

输入

复制
6
2 5 0
3 4 0
6 4 1
4 5 1
1 2 0

输出

复制
5 2 1 4 3 6
1 2 5 3 4 6
1 2 3 6 4 5
5 2 4 1 3 6

说明

\hspace{15pt}在这个样例中,所构建的二叉树如下图所示: