首页 > 代码库 > PAT A 1119. Pre- and Post-order Traversals (30)【二叉树遍历】
PAT A 1119. Pre- and Post-order Traversals (30)【二叉树遍历】
No.1119
题目：由前序后序二叉树序列，推中序，判断是否唯一后输出一组中序序列
思路：前序从前向后找，后序从后向前找，观察正反样例可知，前后序树不唯一在于单一子树是否为左右子树。
判断特征：通过查找后序序列中最后一个结点的前一个在先序中的位置，来确定是否可以划分左右孩子，如果不能， 就将其划分为右孩子（或左孩子），递归建树。
中序遍历输出。
#include <iostream>using namespace std;const int maxn = 31;int n, index = 0;int pre[maxn], post[maxn];bool flag = true;struct Node { int data; Node *lchild, *rchild;} *root;Node *create(int preL, int preR, int postL, int postR) { if (preL > preR) return NULL; Node *node = new Node; node->data = http://www.mamicode.com/pre[preL];" "; else cout << node->data << endl; index++; inOrder(node->rchild);}int main() { cin >> n; for (int i = 0; i < n; ++i) cin >> pre[i]; for (int i = 0; i < n; ++i) cin >> post[i]; root = create(0, n - 1, 0, n - 1); if (flag) cout << "Yes\n"; else cout << "No\n"; inOrder(root); return 0;}PAT A 1119. Pre- and Post-order Traversals (30)【二叉树遍历】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。