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

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;

void dlr(int root);
void ldr(int root);
void lrd(int root);

vector<vector<int> > v;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int n;cin >> n;
    v.resize(n+1);
    int a,b;
    vector<int> nums(n+1);
    for(int i = 1;i<n;i++) {
        cin >> a >> b;
        v[a].emplace_back(b);
        nums[b]++;
    }

    int root;
    for(int i = 1;i<=n;i++) {
        if(nums[i] == 0) {
            root = i;
            break;
        }
    }

    dlr(root);
    cout << endl;
    ldr(root);
    cout << endl;
    lrd(root);
    cout << endl;
}

void dlr(int root) {
    cout << root << ' ';
    int size = v[root].size();
    if(size == 2) {
        if(v[root][0] > v[root][1]) swap(v[root][0],v[root][1]);
        dlr(v[root][0]);dlr(v[root][1]);
    } else if(size == 1) {
        dlr(v[root][0]);
    }
    return;
}

void ldr(int root) {
    int size = v[root].size();
    if(size == 1) {
        if(v[root][0] > root) {
            ldr(v[root][0]);
            cout << root << ' ';
        } else {
            cout << root << ' ';
            ldr(v[root][0]);
        }
    } else if(size == 2) { 
        if(v[root][0] > v[root][1]) swap(v[root][0],v[root][1]);
        ldr(v[root][0]);
        cout << root << ' ';
        ldr(v[root][1]);
    } else {
        cout << root << ' ';
    }
    return;
}

void lrd(int root) {
    int size = v[root].size();
    if(size == 1) {
        lrd(v[root][0]);
    } else if(size == 2) {
        if(v[root][0] > v[root][1]) swap(v[root][0],v[root][1]);
        lrd(v[root][0]);lrd(v[root][1]);
    }
    cout << root << ' ';
}

很简单的题目没得说，很多人记不住前序，中序和后序的区别，实际上，就是根节点在前，在中，在后的区别，同时左节点永远在右节点的前面