问题描述

用先序序列和中序序列构建二叉树，采用二叉链表存储。编写递归算法，交换二叉树的左右子树，
输出新二叉树按先序遍历得到的结果。

提交格式：实现void solve(int n, int *preOrder, int *inOrder, int *outOrder)函数。
函数参数为序列长度n、先序序列preOrder、中序序列inOrder和输出序列outOrder。1<=n<=1000000，树的深度<=2000。请不要printf输出任何内容。

实现思路
测试主函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main()
{
    int N;
    scanf_s("%d", &N);
    int* pre = (int*)malloc(N * sizeof(int));
    if (pre == NULL) return 0;
    int* in = (int*)malloc(N * sizeof(int));
    if (in == NULL) return 0;
    int* out = (int*)malloc(N * sizeof(int));
    if (out == NULL) return 0;
    for (int i = 0; i < N; i++)
    {
        scanf_s("%d", &pre[i]);
    }
    for (int j = 0; j < N; j++)
    {
        scanf_s("%d", &in[j]);
    }
    solve(N, pre, in, out);
    printf("\n");
    return 0;
}
solve函数
1
2
3
4
5
6
7
8
9
10
11
12
13
void solve(int n, int* preOrder, int* inOrder, int* outOrder)
{
    PBiTNode root=NULL;
    if (n <= 0 || preOrder==NULL|| inOrder==NULL|| outOrder==NULL)
    {
        return;
    }
    else
    {
        CreatepostBiTree(preOrder, inOrder, 0, n - 1, 0, n - 1, root);
        PreOrder(root, outOrder);
    }
}
CreatepostBiTree函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void CreatepostBiTree(int preord[], int inord[], int i, int j, int k, int h, PBiTNode &t) 
{
    /* 先序序列中从i到j，中序序列从k到h，建立一棵二叉树放在t中*/
    int m;
    t = (BiTNode*)malloc(sizeof(BiTNode));
    if (t == NULL) return ;
        t->data = preord[i];  /*二叉树的根*/
        m = k;
        while (inord[m] != preord[i]) m++; /*在中序序列中定位树的根*/
        /*递归调用建立左子树*/
        if (m == k) t->lchild = NULL;    /*左子树空*/
        else CreatepostBiTree(preord, inord, i + 1, i + m - k, k, m - 1, (t->lchild));
        /*递归调用建立右子树*/
        if (m == h) t->rchild = NULL;   /*右子树空*/
        else CreatepostBiTree(preord, inord, i + m - k + 1, j, m + 1, h, (t->rchild));
}
PreOrder函数
1
2
3
4
5
6
7
8
9
void PreOrder(PBiTNode bt, int* out1)
{
    if (bt != NULL) { /* 如果bt为空，结束*/
        out1[s++] = bt->data;  /*访问根结点*/
        printf("%d ", bt->data);
        PreOrder(bt->rchild, out1);   /*先序遍历左子树（递归调用）*/
        PreOrder(bt->lchild, out1);   /*先序遍历右子树（递归调用）*/
    }
}
初步实现
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
67
68
69
70
71
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
    int data;
    struct Node* lchild;
    struct Node* rchild;
}BiTNode, * PBiTNode;
int s = 0;
void PreOrder(PBiTNode bt, int* out1);
void CreatepostBiTree(int preord[], int inord[], int i, int j, int k, int h, PBiTNode &t);
void solve(int n, int* preOrder, int* inOrder, int* outOrder)
{
    PBiTNode root=NULL;
    if (n <= 0 || preOrder==NULL|| inOrder==NULL|| outOrder==NULL)
    {
        return;
    }
    else
    {
        CreatepostBiTree(preOrder, inOrder, 0, n - 1, 0, n - 1, root);
        PreOrder(root, outOrder);
    }
}
void CreatepostBiTree(int preord[], int inord[], int i, int j, int k, int h, PBiTNode &t) 
{
    /* 先序序列中从i到j，中序序列从k到h，建立一棵二叉树放在t中*/
    int m;
    t = (BiTNode*)malloc(sizeof(BiTNode));
    if (t == NULL) return ;
        t->data = preord[i];  /*二叉树的根*/
        m = k;
        while (inord[m] != preord[i]) m++; /*在中序序列中定位树的根*/
        /*递归调用建立左子树*/
        if (m == k) t->lchild = NULL;    /*左子树空*/
        else CreatepostBiTree(preord, inord, i + 1, i + m - k, k, m - 1, (t->lchild));
        /*递归调用建立右子树*/
        if (m == h) t->rchild = NULL;   /*右子树空*/
        else CreatepostBiTree(preord, inord, i + m - k + 1, j, m + 1, h, (t->rchild));
}
void PreOrder(PBiTNode bt, int* out1)
{
    if (bt != NULL) { /* 如果bt为空，结束*/
        out1[s++] = bt->data;  /*访问根结点*/
        printf("%d ", bt->data);
        PreOrder(bt->rchild, out1);   /*先序遍历左子树（递归调用）*/
        PreOrder(bt->lchild, out1);   /*先序遍历右子树（递归调用）*/
    }
}
int main()
{
    int N;
    scanf_s("%d", &N);
    int* pre = (int*)malloc(N * sizeof(int));
    if (pre == NULL) return 0;
    int* in = (int*)malloc(N * sizeof(int));
    if (in == NULL) return 0;
    int* out = (int*)malloc(N * sizeof(int));
    if (out == NULL) return 0;
    for (int i = 0; i < N; i++)
    {
        scanf_s("%d", &pre[i]);
    }
    for (int j = 0; j < N; j++)
    {
        scanf_s("%d", &in[j]);
    }
    solve(N, pre, in, out);
    printf("\n");
    return 0;
}
实现要点

1.函数嵌套使用时，参数值的传递。如：

1
void CreatepostBiTree(int preord[], int inord[], int i, int j, int k, int h, PBiTNode &t)

若把t之前的&去掉，则无法完成双向传递，CreatepostBiTree函数执行完后root的值并未修改，运行出错。

2.malloc动态分配内存之后，注意判断是否分配成功

3.solve函数调用CreatepostBiTree函数时，注意根据序列preord和inord的实际情况传入i，j，k，h的实参

1
CreatepostBiTree(preOrder, inOrder, 0, n - 1, 0, n - 1, root);
测试
样例测试

输入样例：
n=5,preOrder={1,2,3,4,5},inOrder={3,2,4,1,5}
输出样例：
outOrder={1,5,2,4,3}

样例测试

提交测试

提交测试

进一步思考

求助

怎么办呢。。怎么办呢。。算了，明天又想，上床睡觉。

我闭上眼，横竖睡不着，翻来覆去地想，脑中浮现着代码，最后从一行行代码间看出了满屏写满了两个大字——哈希！

我惊坐而起，爬下床去，慌忙翻开电脑，把中序遍历的序号进行了Hash👨‍💻

1
2
3
int inordindex[100000000];
for (int i = 0; i < n; i++)
            inordindex[inOrder[i]] = i;
最终实现
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
67
68
69
70
71
72
73
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
    int data;
    struct Node* lchild;
    struct Node* rchild;
}BiTNode, * PBiTNode;
int s = 0;
int inordindex[100000000];
void PreOrder(PBiTNode bt, int* out1);
void CreatepostBiTree(int preord[], int inord[], int i, int j, int k, int h, PBiTNode &t);
void solve(int n, int* preOrder, int* inOrder, int* outOrder)
{
    PBiTNode root=NULL;
    if (n <= 0 || preOrder==NULL|| inOrder==NULL|| outOrder==NULL)
    {
        return;
    }
    else
    {
        for (int i = 0; i < n; i++)
            inordindex[inOrder[i]] = i;
        CreatepostBiTree(preOrder, inOrder, 0, n - 1, 0, n - 1, root);
        PreOrder(root, outOrder);
    }
}
void CreatepostBiTree(int preord[], int inord[], int i, int j, int k, int h, PBiTNode &t) 
{
    /* 先序序列中从i到j，中序序列从k到h，建立一棵二叉树放在t中*/
    int m;
    t = (BiTNode*)malloc(sizeof(BiTNode));
    if (t == NULL) return ;
        t->data = preord[i];  /*二叉树的根*/
        m = inordindex[preord[i]];  /*在中序序列中定位树的根*/
        /*递归调用建立左子树*/
        if (m == k) t->lchild = NULL;    /*左子树空*/
        else CreatepostBiTree(preord, inord, i + 1, i + m - k, k, m - 1, (t->lchild));
        /*递归调用建立右子树*/
        if (m == h) t->rchild = NULL;   /*右子树空*/
        else CreatepostBiTree(preord, inord, i + m - k + 1, j, m + 1, h, (t->rchild));
}
void PreOrder(PBiTNode bt, int* out1)
{
    if (bt != NULL) { /* 如果bt为空，结束*/
        out1[s++] = bt->data;  /*访问根结点*/
        printf("%d ", bt->data);
        PreOrder(bt->rchild, out1);   /*先序遍历左子树（递归调用）*/
        PreOrder(bt->lchild, out1);   /*先序遍历右子树（递归调用）*/
    }
}
int main()
{
    int N;
    scanf_s("%d", &N);
    int* pre = (int*)malloc(N * sizeof(int));
    if (pre == NULL) return 0;
    int* in = (int*)malloc(N * sizeof(int));
    if (in == NULL) return 0;
    int* out = (int*)malloc(N * sizeof(int));
    if (out == NULL) return 0;
    for (int i = 0; i < N; i++)
    {
        scanf_s("%d", &pre[i]);
    }
    for (int j = 0; j < N; j++)
    {
        scanf_s("%d", &in[j]);
    }
    solve(N, pre, in, out);
    printf("\n");
    return 0;
}

ac

舒服了😃