字典序最小的中序遍历 树形DP

题目：https://ac.nowcoder.com/acm/problem/14506
题目大意：

思路：
因为所有点的编号不同，那么我们考虑交换时，如果左子树的中序遍历的第一个编号>如果左子树的中序遍历的第一个编号。那么我们就交换。
所以记录每个点为根的子树的中序遍历的第一个编号就可以了。

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

int l[2000005], r[2000005];
int ans=0;
int DFS(int u){
    int lson=u, rson=u;
    if(l[u]) lson=DFS(l[u]);
    if(r[u]) rson=DFS(r[u]);
    if(lson>rson){
        swap(l[u], r[u]);
        ans++;
    }
    return min(lson, rson);
}
void dfs(int u){
    if(l[u]) dfs(l[u]);
    printf("%d ", u);
    if(r[u]) dfs(r[u]);
}

int  main(){
    int n, root;
    while(~scanf("%d%d", &n, &root)){
        ans=0;
        for(int i=1; i<=n; i++){
            int x, y; scanf("%d%d", &x, &y);
            l[i]=x, r[i]=y;
        }
        DFS(root);
        printf("%d\n", ans);
        dfs(root);
        printf("\n");
    }

    return 0;
}