首页 > 代码库 > 杭电1710 (已知二叉树前中序 求后序)

杭电1710 (已知二叉树前中序 求后序)

#include "iostream"#include "stack"using namespace std;int result[1001];int cnt;/* 得到后序序列 */void getPost(int* pre,int* in,int len) { /* 分别记录当前处理二叉树的前序 后序 和 长度*/	if (len == 0)  /* 前序序列长度为0  直接返回*/		return;  	result[cnt++] = pre[0]; /* 将前序的第一个节点 即当前二叉树的根进入结果数组存储 */	int i;	for (i = 0; in[i] != pre[0]; i++);	getPost(pre+i+1,in+i+1,len-i-1); /* 先递归处理右子树  因为结果要按后序的逆序存储 即为根右左 */	getPost(pre+1,in,i); /* 递归处理左子树  */ }int main() {	int n;	int pre[1001], inOrder[1001];	while (cin >> n) {		cnt = 0;		for (int i = 0; i < n; i++)			cin >> pre[i];		for (int j = 0; j < n; j++) {			cin >> inOrder[j];		}		getPost(pre, inOrder, n);		for (int i = n - 1; i >= 0; i--) {			if (i == n - 1)				cout << result[i];			else				cout << " " << result[i];		}		cout << endl;	}	return 0;}

  

杭电1710 (已知二叉树前中序 求后序)