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

相关推荐

野猪不是猪🐗:现在的环境就是这样,供远大于求。 以前卡学历,现在最高学历不够卡了,还要卡第一学历。 还是不够筛,于是还要求得有实习、不能有gap等等... 可能这个岗位总共就一个hc,筛到最后还是有十几个人满足这些要求。他们都非常优秀,各方面都很棒。 那没办法了,看那个顺眼选哪个呗。 很残酷,也很现实
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务