题解 | 先序遍历、中序遍历和后序遍历

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

void pre(int root,const vector<int>& left,const vector<int>& right){
    if(root==0){
        return;
    }
    cout<<root<<" ";
    pre(left[root],left,right);
    pre(right[root],left,right);
}

void in(int root,const vector<int>& left,const vector<int>& right){
    if(root==0){
        return;
    }
    in(left[root],left,right);
    cout<<root<<" ";
    in(right[root],left,right);
}

void post(int root,const vector<int>& left,const vector<int>& right){
    if(root==0){
        return;
    }
    post(left[root],left,right);
    post(right[root],left,right);
    cout<<root<<" ";
}

int main() {
    int n;
    cin>>n;
    vector<int>left(n+1,0),right(n+1,0);
    vector<vector<int>>tree(n+1);
    vector<bool>parent(n+1,false);
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        tree[a].push_back(b);
        parent[b]=true;
    }
    int root;
        // 为每个父节点分配左右孩子
    for(int i = 1; i <= n; i++) {
        if(tree[i].size() == 1) {
            // 只有一个孩子
            if(tree[i][0] > i) {
                left[i] = tree[i][0]; // 子节点编号大于父节点，视为左孩子
            } else {
                right[i] = tree[i][0]; // 否则视为右孩子
            }
        } else if(tree[i].size() == 2) {
            // 有两个孩子，按编号排序
            sort(tree[i].begin(), tree[i].end());
            left[i] = tree[i][0]; // 编号较小者为左孩子
            right[i] = tree[i][1]; // 编号较大者为右孩子
        }
        if(!parent[i]){
            root=i;
        }
    }
    pre(root, left, right);
    cout<<endl;
    in(root, left, right);
    cout<<endl;
    post(root, left, right);

    return 0;
}