题解

#include <bits/stdc++.h>
using namespace std;
class TreeNode {  //定义树节点 
public:
    int name;
    vector<TreeNode*> children;
    TreeNode(const int& nodeName) : name(nodeName) {}
    void addChild(TreeNode* child){
        children.push_back(child);
    }
};
// 前序遍历
void preorder_traversal(TreeNode* node) {
    if (node == nullptr)
        return;
    cout << node->name << " ";
    for (TreeNode* child : node->children)
        preorder_traversal(child);
}
// 中序遍历
void inorder_traversal(TreeNode* node) {
    if (node == nullptr)
        return;
    if (node->children.size() > 0) {
        inorder_traversal(node->children[0]);
    }
    cout << node->name << " ";
    for (size_t i = 1; i < node->children.size(); ++i) {
        inorder_traversal(node->children[i]);
    }
}
// 后序遍历
void postorder_traversal(TreeNode* node) {
    if (node == nullptr)
        return;
    for (TreeNode* child : node->children)
        postorder_traversal(child);
    cout << node->name << " ";
}
int main() {
    int n, j, k;
    string flag;
    cin >> n >> flag;
    vector<TreeNode*> nodes(n + 1);  //创建一个存储节点的 vector，索引从1开始
    nodes[0] = new TreeNode(0);  //根节点
    for (int i = 1; i <= n; i++) {
        nodes[i] = new TreeNode(i);  //将新节点添加到 vector
    }
    for (int i = 0; i < n; i++) {
        cin >> j >> k;
        nodes[j]->addChild(nodes[k]);  //根据索引添加子节点
    }
    if (flag == "first")
    	preorder_traversal(nodes[0]);
    else if (flag == "second")
		inorder_traversal(nodes[0]);
	else
    	postorder_traversal(nodes[0]);
    // 释放内存
    for (TreeNode* node : nodes)
        delete node;
    return 0;
}