#include <bits/stdc++.h> using namespace std; int main(){

#include #include #include using namespace std; vector<vector> children; // 邻接表存储子节点 vector pre, post, level, leaves; // 先序遍历：根 -> 子节点（按输入顺序） void preOrder(int u) { pre.push_back(u); for (int v : children[u]) { preOrder(v); } } // 后序遍历：子节点（按输入顺序） -> 根 void postOrder(int u) { for (int v : children[u]) { postOrder(v); } post.push_back(u); } // 层序遍历：广度优先遍历 void levelOrder(int root) { queue q; q.push(root); while (!q.empty()) { int u = q.front(); q.pop(); level.push_back(u); for (int v : children[u]) { q.push(v); } } } // 收集叶子节点：无子节点的节点 void findLeaves(int u) { if (children[u].empty()) { leaves.push_back(u); return; } for (int v : children[u]) { findLeaves(v); } } int main() { int n; cin >> n; children.resize(n + 1); vector isRoot(n + 1, true); // 标记根节点 // 构建邻接表并确定根节点 for (int i = 1; i <= n; ++i) { int L, R; cin >> L >> R; if (L != 0) { children[i].push_back(L); isRoot[L] = false; } if (R != 0) { children[i].push_back(R); isRoot[R] = false; } } // 寻找根节点 int root = 0; for (int i = 1; i <= n; ++i) { if (isRoot[i]) { root = i; break; } } // 遍历 preOrder(root); postOrder(root); levelOrder(root); findLeaves(root); // 输出结果 cout << "先序遍历："; for (size_t i = 0; i < pre.size(); ++i) { if (i > 0) cout << " "; cout << pre[i]; } cout << "\n后序遍历："; for (size_t i = 0; i < post.size(); ++i) { if (i > 0) cout << " "; cout << post[i]; } cout << "\n层序遍历："; for (size_t i = 0; i < level.size(); ++i) { if (i > 0) cout << " "; cout << level[i]; } cout << "\n叶子遍历："; for (size_t i = 0; i < leaves.size(); ++i) { if (i > 0) cout << " "; cout << leaves[i]; } cout << endl; return 0; }