C++14(g++5.4) 解法, 执行用时: 154ms, 内存消耗: 26528K, 提交时间: 2020-03-07 21:17:21

#include<bits/stdc++.h>
using namespace std;
const int MX=2e6+9;
int n,rt,tim=0;
int l[MX],r[MX];

int dfs(int t){
    int a=t,b=t;
    if( l[t] ) a=dfs(l[t]);
    if( r[t] ) b=dfs(r[t]);
    if( a>b ){
        swap(l[t],r[t]);
        tim++;
    }
    return min(a,b);
}

void print(int x){
    if( l[x]!=0 )
        print(l[x]);
    printf("%d ",x);
    if( r[x]!=0 )
        print(r[x]);
}

int main()
{
    //freopen("input.txt","r",stdin);
    scanf("%d %d",&n,&rt);
    for( int i=1 ; i<=n ; i++ )
        scanf("%d %d",&l[i],&r[i]);
    dfs(rt);
    printf("%d\n",tim);
    print(rt);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 272ms, 内存消耗: 27548K, 提交时间: 2020-08-18 13:54:51

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+50;
int n,root,l[maxn],r[maxn],ans;
int dfs(int x)
{
	int L=x,R=x;
	if(l[x])L=dfs(l[x]);
	if(r[x])R=dfs(r[x]);
	if(L>R)
	{
		swap(l[x],r[x]);
		ans++;
	}
	return min(L,R);
}
void PrintMid(int x)
{
	if(l[x])
		PrintMid(l[x]);
	cout<<x<<' ';
	if(r[x])
		PrintMid(r[x]);
}
int main()
{
	cin>>n>>root;
	for(int i=1;i<=n;i++)cin>>l[i]>>r[i];
	dfs(root);
	cout<<ans<<endl;
	PrintMid(root);
	cout<<endl;
	return 0;
}