U537745 【模板】二叉树的遍历
题目描述
对于给定的二叉树，你需要维护：
$\texttt{1.}\,$二叉树的先序遍历；
$\texttt{2.}\,$二叉树的中序遍历；
$\texttt{3.}\,$二叉树的后序遍历；
$\texttt{4.}\,$二叉树的层序遍历。
**由于输出数据过多，请使用较快的 IO 方式！**
输入格式
第一行输入一个整数 $n\left(1\leq n\leq 5 \times 10^5\right)$ 代表二叉树的节点数量。
此后 $n-1$ 行，每行输入三个整数 $u, v, op \left(1\leq u, v\leq n; 0 \leq op \leq 1 \right)$ 代表当前节点 $u$ 的父节点为 $v$ ，其中 $op = 0$ 代表当前节点是父节点的左儿子，$op = 1$ 代表当前节点是父节点的右儿子。
输出格式
在第一行上输出 $n$ 个整数，代表二叉树的先序遍历；
在第二行上输出 $n$ 个整数，代表二叉树的中序遍历；
在第三行上输出 $n$ 个整数，代表二叉树的后序遍历；
在第四行上输出 $n$ 个整数，代表二叉树的层序遍历。
说明/提示
在这个样例中，所构建的二叉树如下图所示：
