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

题目坑点还挺多，因此写个题解记录一下。

坑点1：单向边，dfs u到v的时候与双向边不同即不需要加判断v!=fa，特判节点孩子情况的时候也与双向边不同

坑点2：没告诉根节点，需要自己找入度为0的点作为根节点

坑点3：节点单孩子的情况特殊，孩子节点值大于自身值才作为左孩子，否则为右孩子

坑点4：节点有两个孩子的情况，左右孩子的判断是基于两个孩子的节点值大小判断

我习惯使用vector作邻接表建边，这样先序和后序使用dfs非常容易实现，而中序dfs需要多些判断。

对于节点两个孩子的情况，我们对邻接表adj[i]进行从小到大排序，i取遍1~n，这样在dfs遍历出边的时候，第一个遍历到的一定是左孩子节点，第二个遍历到的是右孩子节点。

#include <iostream>
#include <vector>
#include <algorithm>

void solve(){
    int n;
    std::cin >> n;

    std::vector<std::vector<int>> adj(n+1);//邻接表
    std::vector<int> in(n+1);//入度
    for(int i = 1; i < n; i++){
        int u,v;
        std::cin >> u >> v;

        adj[u].push_back(v);//建立u->v的边
        in[v]++;//v的入度+1
    }

    int root = -1;//根节点
    for(int i = 1; i <= n; i++){
        if(in[i] == 0){
            root = i;//根节点为入度为0的点
        }
    }

    for(int i = 1; i <= n; i++){//对邻接表排序
        std::sort(adj[i].begin(),adj[i].end());
    }

    auto dfs1 = [&](auto &&self1,int u)->void {
        //先序:根 左 右
        std::cout << u << " ";

        for(auto v:adj[u]){
            self1(self1,v);
        }
    };

    dfs1(dfs1,root);//从根节点开始先序遍历
    std::cout << "\n";

    auto dfs2 = [&](auto &&self2,int u)->void {
        //中序:左 根 右
        if(adj[u].size() == 0){//u为叶子节点，直接打印u并return
            std::cout << u << " ";
            return;
        }
        if(adj[u].size() == 1){//u只有一个孩子
            int v = adj[u].front();//v为唯一孩子
            if(v > u){//若v为左孩子，先访问左孩子，再访问根
                self2(self2,v);
                std::cout << u << " ";
            }else{//若v为右孩子，先访问根，再访问右孩子
                std::cout << u << " ";
                self2(self2,v);
            }
            return;
        }

        //u有两个孩子
        bool hasLeft = false;//表示左孩子是否已经访问完毕
        for(auto v:adj[u]){
            if(hasLeft){//若左孩子已经访问结束，则需要先访问根
                std::cout << u << " ";
            }
            self2(self2,v);
            hasLeft = true;//第一次循环结束后，该标志位会被置为true
        }
    };

    dfs2(dfs2,root);//从根节点开始中序遍历
    std::cout << "\n";

    auto dfs3 = [&](auto &&self3,int u)->void {
        //后序:左 右 根
        for(auto v:adj[u]){
            self3(self3,v);
        }
        std::cout << u << " ";
    };

    dfs3(dfs3,root);//从根节点开始后序遍历
    std::cout << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int T = 1;
    // std::cin >> T;
    for(; T--;){
        solve();
    }

    return 0;
}