字典序最小的中序遍历 树形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;
}
全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务