PAT甲级：A1119 Pre- and Post-order Traversals (30分)

Suppose that all the keys in a binary tree are distinct positive integers. A unique binary tree can be determined by a given pair of postorder and inorder traversal sequences, or preorder and inorder traversal sequences. However, if only the postorder and preorder traversal sequences are given, the corresponding tree may no longer be unique.

Now given a pair of postorder and preorder traversal sequences, you are supposed to output the corresponding inorder traversal sequence of the tree. If the tree is not unique, simply output any one of them.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤ 30), the total number of nodes in the binary tree. The second line gives the preorder sequence and the third line gives the postorder sequence. All the numbers in a line are separated by a space.

Output Specification:

For each test case, first printf in a line Yes if the tree is unique, or No if not. Then print in the next line the inorder traversal sequence of the corresponding binary tree. If the solution is not unique, any answer would do. It is guaranteed that at least one solution exists. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input 1:

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

Sample Output 1:

1
2
Yes
2 1 6 4 7 3 5

Sample Input 2:

1
2
3
4
1 2 3 4
2 4 3 1

Sample Output 2:

1
2
No
2 1 3 4
  • 题意：已知给定一个二叉树的前中序序列或后中序遍历序列能唯一确定一棵二叉树。现在给定一棵二叉树的前序和后序遍历序列，判断能否复原一棵二叉树，或者如果存在多个满足条件的二叉树，则输出任意一个中序遍历序列。
  • 分析：先拿先序遍历举例，根据先序遍历的递归特性，一棵二叉树的先序遍历序列总会被分为3个部分【根+左子树先序序列+右子树先序序列】，后序遍历序列正好相反【左子树后序序列+右子树后序序列+根】，因此实际上先序遍历的根，它的右边一个数的就是这棵树左子树的根，之后在后序序列中找到这个数temp，那么后序序列的第一个数到temp这个数为止就是这颗树的左子树，因此就能将左右子树划分出来了，那什么时候是不能确定的呢？就是上面找到的temp在后序遍历序列的倒数第二个位置时就是不能确定的，因为它既可以做左子树又可以做右子树。最后不确定情况全当做左子树或者右子树，这样最后就能至少确定一棵树了（如果存在）。
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
#include <bits/stdc++.h>
using namespace std;
const int N = 35;
int pre[N], post[N], n;
vector<int> ansIn;
bool isunique = true;
void create(int prel, int prer, int postl, int postr) {
    if (prel > prer) return;
    if (prel == prer) {
        ansIn.push_back(pre[prel]);
        return;
    }
    int k = postl;
    while (post[k] != pre[prel + 1]) k++;
    int numRight = postr - k - 1;
    if (numRight == 0) isunique = false;
    create(prel + 1, prer - numRight, postl, k);
    ansIn.push_back(pre[prel]);
    create(prer - numRight + 1, prer, k + 1, postr - 1);
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &pre[i]);
    for (int i = 0; i < n; i++) scanf("%d", &post[i]);
    create(0, n - 1, 0, n - 1);
    printf("%s\n", isunique ? "Yes" : "No");
    for (int i = 0; i < ansIn.size(); i++) {
        if (i != 0) printf(" ");
        printf("%d", ansIn[i]);
    }
    printf("\n");
    return 0;
}