PAT甲级1119. Pre- and Post-order Traversals

题意：

假设二叉树中的所有键都是不同的正整数。一个唯一的二进制树可以通过给定的一对后序和顺序遍历序列来确定，也可以通过预序和顺序遍历序列来确定。然而，如果仅给出了后序和预序遍历序列，则相应的树可能不再是唯一的。

现在给出一对postorder和preorder遍历序列，你应该输出树的相应的顺序遍历序列。如果树不是唯一的，只需输出任何一个树。

输入规格：

每个输入文件包含一个测试用例。对于每种情况，第一行给出正整数N（<= 30），

二叉树中的节点总数。第二行给出了预订序列，第三行给出了后序序列。一行中的所有数字都以空格分隔。

输出规格：

对于每个测试用例，如果树是唯一的，则第一个printf为“是”，否则为“否”。

然后在下一行打印相应二叉树的顺序遍历序列。如果解决方案不是唯一的，任何答案都可以。保证至少有一个解决方案存在。一行中的所有数字必须只有一个空格分开，并且行尾不能有额外的空格。

思路：

二叉树的构造和遍历。题目感觉比较有点毛病。1A总让我感觉怪怪的。

ac代码：

C++

// pat1119.cpp : 定义控制台应用程序的入口点。

//

#include "stdafx.h"

#include<iostream>

#include<cstdio>

#include<string>

#include<algorithm>

#include<queue>

#include<vector>

#include<cstring>

#include<stdio.h>

#include<map>

#include<cmath>

#include<unordered_map>

#include<unordered_set>

using namespace std;

int n;

int pre[31];

int post[31];

int in[31];

struct TreeNode

{

	int val;

	TreeNode* left;

	TreeNode* right;

	TreeNode(int x) : val(x) , left(NULL) , right(NULL) {}

};

bool flag = true;

TreeNode* build(int prel, int prer, int postl, int postr)

{

	if (prel > prer || postl > postr) return NULL;

	TreeNode* root = new TreeNode(pre[prel]);

	prel++;

	postr--;

	if (prel > prer || postl > postr) return root;

	int temp = postl;

	while (temp <= postr && post[temp] != pre[prel]) temp++;

	root->left = build(prel, prel + temp - postl, postl, temp);

	if (temp == postr)

	{

		flag = false;

		return root;

	}

	prel = prel + temp - postl + 1;

	postl = temp + 1;

	temp = postl;

	while (temp < postr && post[temp] != pre[prel]) temp++;

	root->right = build(prel, prel + temp - postl, postl, temp);

	return root;

}

void inorder(TreeNode* root)

{

	if (!root) return;

	static int pos = 0;

	inorder(root->left);

	in[pos++] = root->val;

	inorder(root->right);

}

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]);

	TreeNode* root = build(0, n - 1, 0, n - 1);

	inorder(root);

	if (flag) printf("Yes\n");

	else printf("No\n");

	for (int i = 0; i < n - 1; i++)

		printf("%d ", in[i]);

	printf("%d\n", in[n - 1]);

    return 0;

}