C/C++数据结构——字典序最小的中序遍历

题目描述

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

给一个有根二叉树,可以无限次的交换任意节点的左右子树,问最少交换多少次使得该树的中序遍历的字典序最小?

输入描述:

每个测试点有仅有一组数据 每组测试数据的一行有两个整数N,M,代表有N个节点,M为根节点。
接下来N行,每行两个整数ai,bi.ai表示第i个节点的左儿子,bi表示第i个节点的右儿子.

N∈[1,5×10⁵] ai,bi,M∈[1,N] 当ai,bi为0时 表示空节点.

输出描述:

输出两行
第一行 为最小交换次数.
第二行 为字典序最小的中序遍历.

示例1

输入

7 4
0 0
1 3
0 0
2 5
6 7
0 0
0 0

输出

0
1 2 3 4 6 5 7

解题代码

#include
#include
#include
#define MAXSIZE 5*100005
typedef struct treeNode{
    int x;
    struct treeNode *L_child,*R_child;
}node;
typedef struct nums{
    int l,r;
}num;
num input[500005];
int cost=0;
node* createNode(int m)
{
    if(m==0){
        return NULL;
    }
    node *root;
    root=(node*)malloc(sizeof(node));
    root->x=m;
    root->L_child=createNode(input[m].l);
    root->R_child=createNode(input[m].r);
    return root;
}
int numChange(node *root)
{
	//if(root==NULL)return 0;
    int minL,minR;
    minL=minR=root->x;
    if(root->L_child!=NULL)
    	minL=numChange(root->L_child);
    if(root->R_child!=NULL)
    	minR=numChange(root->R_child);
    if(minL>minR){
    	cost++;
        node *temp = root->L_child;
        root->L_child=root->R_child;
        root->R_child=temp;
    }
    
    return minL<minR?minL:minR;
}

void LNR(node *root)
{
    if(root==NULL){
        return;
    }
    LNR(root->L_child);
    printf("%d ",root->x);
    LNR(root->R_child);
}
int main()
{
    int n,m,x,y;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&input[i].l,&input[i].r);
    }
    node *root;
    root=createNode(m);
    numChange(root);
    printf("%d\n",cost);
    LNR(root);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

解题思路

这道题目其实可以不用链二叉树去做，可以直接用树形数组结构去做，其实只要一个num结构体就能够满足做题需求，但是我还是把它弄成了链二叉树做，导致我的内存比别人的稍微大一些。
这关于树形结构的练习，难点就在于什么时候交换，其实题目给出的要求已经很简单了，都是数字且左右子树都规定，建树后，只需要比较结点的左右子树的最小值，如果左子树的最小值大于右子树的最小值，那么就交换，中序遍历按照左中右的顺序遍历，所以左边的先遍历，左子树的结点值如果大的话那么字典序必然大。

关于限制推荐，我不知道文章是出了啥问题，CSDN的发文规范搞得太无语了，真的是。