题目要看仔细，判断两次，成功输出后序，不成功输出NO 注：左是小于，右是大于等于
#include<iostream>#include<stdlib.h>#define INF 0x3f3f3f#PRagma warning(disable:4996)using namespace std;int N;int comp;bool flag;struct node{ int data; node *l, *r;};node *e;void postorder(node *&a)//后序输出二叉树{ if (a->l != NULL) postorder(a->l); if (a->r != NULL) postorder(a->r); if (a==e) printf("%d/n", a->data); else printf("%d ", a->data);}void preorder(int low, int high)//根据前序及排列树建立二叉树 { if (!flag)return; if (low == high) { return; } int mid=-1; for (int t = low + 1;t <= high;t++) if ((e + t)->data >= (e + low)->data) {mid = t;break;} if (mid == -1) {(e + low)->l = e + low + 1;preorder(low + 1, high );} else { for (int t = mid+1;t <= high;t++) if ((e + t)->data < (e + low)->data) {flag = false;return;} if (mid == low + 1) { (e + low)->r = e + mid;preorder(mid, high ); } else { (e + low)->l = e + low + 1;preorder(low + 1, mid - 1 ); (e + low)->r = e + mid;preorder(mid, high ); } }}void preorder2(int low, int high)//镜像建立{ if (!flag)return; if (low == high) { return; } int mid = -1; for (int t = low + 1;t <= high;t++) if ((e + t)->data < (e + low)->data) { mid = t;break; } if (mid == -1) { (e + low)->l = e + low + 1;preorder2(low + 1, high ); } else { for (int t = mid+1;t <= high;t++) if ((e + t)->data >= (e + low)->data) { flag = false;return; } if (mid == low + 1) { (e + low)->r = e + mid;preorder2(mid, high ); } else { (e + low)->l = e + low + 1;preorder2(low + 1, mid - 1 ); (e + low)->r = e + mid;preorder2(mid, high ); } }}int main(){ cin >> N; e = (node *)malloc(sizeof(node)*N); for (int t = 0;t < N;t++) { cin >> (e + t)->data;(e + t)->l = (e + t)->r = NULL; } flag = true; preorder(0, N - 1); if (!flag) { flag = true;preorder2(0, N - 1); } if (!flag) cout << "NO" << endl; else { cout << "YES" << endl; postorder(e); }}新闻热点
疑难解答
