【PAT甲级 - C++题解】1119 Pre- and Post-order Traversals

1119 Pre- and Post-order Traversals

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:

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

Sample Output 1:

Yes
2 1 6 4 7 3 5

Sample Input 2:

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

Sample Output 2:

No
2 1 3 4

题意

给定一组前序遍历和后序遍历，请你输出对应二叉树的中序遍历。

如果树不是唯一的，则输出任意一种可能树的中序遍历即可。

思路

由于结果可能不唯一，所以我们可以直接暴力枚举所有情况，以左子树包含的结点数量为依据进行枚举：

每次递归都要先判断是否满足条件，如果 l1 > r1 ，则说明当前子树已经遍历完，直接返回 1 即可；如果 pre[l1] != post[r2] ，则说明当前这种遍历情况不能构成二叉树，因为前序遍历数组的第一个和后序遍历数组的最后一个元素都是根结点，所以两者必须相等。

遍历左子树包含结点的数量，只要发现合法方案的数量大于一个，就直接退出循环，因为题目只要求输出其中一种合法情况即可。计算合法方案的方法是，获得左子树的合法方案数以及右子树的合法方案数，让两者相乘就是当前遍历情况的合法方案数了。

如果当前情况是满足条件的，就将当前结点加入结果集当中，因为题目要求输出中序遍历结果，所以我们要获得左子树和右子树的中序遍历结果，然后往中间插入当前结点即可。注意，这里用到了 to_string 库函数，它的作用是将数字转换成字符串。

最后判断合法方案数是否唯一，然后输出中序遍历结果。注意，末尾不能有空格，需要手动去掉。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 40;
int n;
int pre[N], post[N];
int dfs(int l1, int r1, int l2, int r2, string& in)
{
    if (l1 > r1)   return 1;
    if (pre[l1] != post[r2])   return 0;   //判断根结点是否相等
    int cnt = 0;
    for (int i = l1; i <= r1; i++) //遍历左子树包含的结点数量
    {
        string lin, rin; //记录左右子树中序遍历的结果
        int lcnt = dfs(l1 + 1, i, l2, l2 + i - l1 - 1, lin);  //记录左子树的合法方案数
        int rcnt = dfs(i + 1, r1, l2 + i - l1 - 1 + 1, r2 - 1, rin);  //记录右子树的合法方案数
        if (lcnt && rcnt)
        {
            in = lin + to_string(pre[l1]) + " " + rin;  //往结果集中加入当前结点
            cnt += lcnt * rcnt; //记录有多少合法方案数
            if (cnt > 1) break; //剪枝，只要方案数大于1个，就直接break
        }
    }
    return cnt;
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)    cin >> pre[i];
    for (int i = 0; i < n; i++)    cin >> post[i];
    string in;
    int cnt = dfs(0, n - 1, 0, n - 1, in);
    if (cnt == 1)    puts("Yes"); //方案唯一
    else    puts("No");   //方案不唯一
    in.pop_back();  //去掉末尾空格
    cout << in << endl;
    return 0;
}