首页 > 代码库 > 杭电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 (已知二叉树前中序 求后序)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。