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

#include <bits/stdc++.h>
using namespace std;

// 定义二叉树节点结构，存储每个节点的左孩子和右孩子（0表示无对应孩子节点）
struct k{
    int left=0;
    int right=0;
};

// 邻接表存储整棵二叉树，索引对应节点编号，存储该节点的左右孩子信息
vector<k>adj;

// 存储所有子节点的无序集合，用于后续查找根节点（根节点无父节点，不会出现在此集合中）
unordered_set<int> root;

// 前序遍历（DFS实现）：算法思想 - 根节点 → 左子树 → 右子树
void dfs1(int x){
    // 第一步：访问当前根节点
    printf("%d ",x);
    // 第二步：递归遍历左子树（左孩子存在则继续深入）
    if(adj[x].left!=0){
        dfs1(adj[x].left);
    }
    // 第三步：递归遍历右子树（右孩子存在则继续深入）
    if(adj[x].right!=0){
        dfs1(adj[x].right);
    }
}

// 中序遍历（DFS实现）：算法思想 - 左子树 → 根节点 → 右子树
void dfs2(int x){
    // 第一步：递归遍历左子树（左孩子存在则继续深入）
    if(adj[x].left!=0){
        dfs2(adj[x].left);
    }
    // 第二步：访问当前根节点
    printf("%d ",x);
    // 第三步：递归遍历右子树（右孩子存在则继续深入）
    if(adj[x].right!=0){
        dfs2(adj[x].right);
    }
}

// 后序遍历（DFS实现）：算法思想 - 左子树 → 右子树 → 根节点
void dfs3(int x){
    // 第一步：递归遍历左子树（左孩子存在则继续深入）
    if(adj[x].left!=0){
        dfs3(adj[x].left);
    }
    // 第二步：递归遍历右子树（右孩子存在则继续深入）
    if(adj[x].right!=0){
        dfs3(adj[x].right);
    }
    // 第三步：访问当前根节点
    printf("%d ",x);
}

int main() {
    int n;
    cin>>n;
    // 初始化二叉树邻接表大小，适配节点编号1~n，避免索引越界
    adj.resize(n+1);
    
    // 算法步骤：读取n-1条边，构建二叉树并标记所有子节点
    for(int i=1;i<=n-1;i++){
        int u,v;
        cin>>u>>v;
        
        // 标记v为子节点（v有父节点u），存入无序集合供后续找根节点使用
        root.insert(v);
        
        // 插入节点核心思路：根据u和v的大小关系，维护u的左右孩子有序性，完成二叉树构建
        if(u<v){
            // 情况1：u的左孩子已存在，且新节点v大于当前左孩子 → v作为右孩子
            if(adj[u].left!=0&&v>adj[u].left){
                adj[u].right=v;
            }
            // 情况2：u的左孩子已存在，且新节点v小于当前左孩子 → 原有左孩子移为右孩子，v作为新左孩子
            else if(adj[u].left!=0&&v<adj[u].left){
                adj[u].right=adj[u].left;
                adj[u].left=v;
            }
            // 情况3：u的右孩子已存在（左孩子无/已调整）→ 原有右孩子移为左孩子，v作为新右孩子
            else if(adj[u].right!=0){
                adj[u].left=adj[u].right;
                adj[u].right=v;
            }
            // 情况4：u无任何孩子 → v直接作为左孩子
            else{
                adj[u].left=v;
            }
        }
        else{
            // 情况1：u的左孩子已存在 → v直接作为右孩子
            if(adj[u].left!=0){
                adj[u].right=v;
            }
            // 情况2：u的右孩子已存在，且新节点v小于当前右孩子 → 原有右孩子移为左孩子，v作为新右孩子
            else if(adj[u].right!=0&&v<adj[u].right){
                adj[u].right=adj[u].left;
                adj[u].left=v;
            }
            // 情况3：u的右孩子已存在，且新节点v大于当前右孩子 → 原有右孩子移为左孩子，v作为新右孩子
            else if(adj[u].right!=0&&v>adj[u].right){
                adj[u].left=adj[u].right;
                adj[u].right=v;
            }
            // 情况4：u无任何孩子 → v直接作为右孩子
            else{
                adj[u].right=v;
            }
        }
    }
    
    // 算法步骤：查找根节点（核心思想：根节点是唯一无父节点的节点，即不在子节点集合中）
    int r;
    for(int i=1;i<=n;i++){
        if(root.count(i)==0){
            r=i;
            break;
        }
    }
    
    // 算法步骤：以根节点为起点，分别执行前序、中序、后序遍历，输出遍历结果
    dfs1(r);
    cout<<endl;
    dfs2(r);
    cout<<endl;
    dfs3(r);
    cout<<endl;
    
    return 0;
}