POJ 2255 解题报告

本文主要是介绍POJ 2255 解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这道题是从前序和中序遍历产生后序遍历。已经做过多次，但是还是写得很麻烦。主要纠结在递归找到root后应该写在后序遍历序列的什么位置。无奈之下又记录了后续遍历的前后范围。

但是实际上，这道题只要输出就好了，所以可以在递归地调左子树和右子树之后直接输出。这样省了空间，看着也简单。另外，c里面指针可以做运算的，这意味着只需要改变指针到新的初始位置，并记录长度即可（每次操作，中序遍历和前序遍历的序列长度必须是一样的）。

具体见http://poj.org/showmessage?message_id=170953中的讨论。

thestoryofsnow

2255

Accepted

176K

0MS

C++

1565B

/* 
ID: thestor1 
LANG: C++ 
TASK: poj2255 
*/
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <limits>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cassert>using namespace std;const int MAXN = 30;void buildPostOrder(char preorder[], int p1, int p2, char inorder[], int i1, int i2, char postorder[], int r1, int r2)
{assert (p2 - p1 == i2 - i1);if (p1 > p2){return;}// printf("preorder[%d, %d]\n", p1, p2);// for (int i = p1; i <= p2; ++i)// {// 	printf("%c", preorder[i]);// }// printf("\n");// printf("inorder[%d, %d]\n", i1, i2);// for (int i = i1; i <= i2; ++i)// {// 	printf("%c", inorder[i]);// }// printf("\n");char root = preorder[p1];for (int i = i1; i <= i2; ++i){if (inorder[i] == root){postorder[r2] = root;int ll = i - 1  - i1 + 1;buildPostOrder(preorder, p1 + 1, p1 + 1 + ll - 1, inorder, i1, i - 1, postorder, r1, r1 + ll - 1);buildPostOrder(preorder, p1 + 1 + ll - 1 + 1, p2, inorder, i + 1, i2, postorder, r1 + ll - 1 + 1, r2 - 1);break;}}
}int main()
{char preorder[MAXN], inorder[MAXN], postorder[MAXN];while (scanf("%s%s", preorder, inorder) == 2){// printf("[%s][%s]\n", preorder, inorder);int len = strlen(preorder);int p = len - 1;buildPostOrder(preorder, 0, len - 1, inorder, 0, len - 1, postorder, 0, len - 1);postorder[len] = '\0';printf("%s\n", postorder);}return 0;
}

这篇关于POJ 2255 解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---