PTA（树和二叉树）2-1 玩转二叉树

2-1 玩转二叉树

分数 6

作者 陈越

单位 浙江大学

给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。

输入格式：

输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。

输出格式：

在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：

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

输出样例：

1
4 6 1 7 5 3 2

答案

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
74
75
#include <iostream>
#include <queue>

using namespace std;

// 定义二叉树结构
typedef struct BiTNode {
    int data;
    BiTNode *lchild, *rchild;
    BiTNode(int data, BiTNode *lchild, BiTNode *rchild) {
        this->data = data;
        this->lchild = lchild;
        this->rchild = rchild;
    }
};

//  根据先序序列和中序序列确定二叉树，pre是指向后序序列数组首元素的指针，in是指向中序序列数组首元素的指针 ，n是结点总数
BiTNode* CreateBiTree (int *pre, int *in, int n) {
    if (n == 0) {
        return NULL;
    }
    // 先序的第一个是根节点
    BiTNode *root =new BiTNode(pre[0], NULL, NULL);

    // 在中序中寻找根节点，则该根节点左右就是其左右子树
    int rootIndex = pre[0];
    for (rootIndex = 0; rootIndex < n; ++rootIndex) {
        if (in[rootIndex] == pre[0]) {
            break;
        }
    }
    // 确定了左右字数方位，开始递归
    // 递归构建反转左子树
    root->lchild = CreateBiTree(pre + rootIndex + 1, in + rootIndex + 1, n - rootIndex - 1);
    // 递归构建反转右子树
    root->rchild = CreateBiTree(pre + 1, in, rootIndex);
    return root;
}

int main() {
    int N;
    cin >> N;
    int in[N], pre[N]; // 用于储存先序和中序序列
    for (int i = 0; i < N; ++i) {
        cin >> in[i];
    }
    for (int i = 0; i < N; ++i) {
        cin >> pre[i];
    }

    // 创建反转的二叉树
    BiTNode *BT = CreateBiTree(pre, in, N);

    // 层次遍历
    queue<BiTNode*> queue; // 将指向树节点的指针放入
    queue.push(BT);
    bool isFirst = true;
    while (!queue.empty()) {
        // 依次遍历队列中的指向树节点的指针
        BiTNode *p = queue.front();
        if (!isFirst) {
            cout << " " << p->data;
        } else {
            cout << p->data;
            isFirst = false;
        }
        queue.pop();
        if (p->lchild != NULL) {
            queue.push(p->lchild);
        }
        if (p->rchild != NULL) {
            queue.push(p->rchild);
        }
    }
}
  1. 输入处理：读取节点数量 N，以及中序遍历序列in和先序遍历序列pre。
  2. 构建二叉树：
    • 递归函数CreateBiTree利用先序（根→左→右）和中序（左→根→右）的特性构建树。
    • 先序首元素为根节点，在中序中找到根节点位置rootIndex，分割出左（长度rootIndex）、右（长度n-rootIndex-1）子树。
    • 递归构建左、右子树（注意原代码此处参数写反，需修正）。
  3. 层次遍历：用队列实现，依次输出节点值，按层打印树结构。