复习版

#include <stdio.h>
#include <stdlib.h>

#define not !
#define and &&
#define or ||

#define ri register int
#define rep(inc, frm, to) for (ri inc = frm; inc < (to); ++inc)
#define rep2(inc, frm, to) for (ri inc = frm; inc > (to); --inc)

#define setbit(x, y) x |= 1 << y
#define clrbit(x, y) x &= ~(1 << y)
#define getbit(x, y) x >> y & 1
#define flipbit(x, y) x ^= 1 << y
#define show_bin(x) { rep2(i, 31, ~0) printf("%d%c", getbit(x, i), i ? 9 : 10); }

#define min(a, b) (a < b ? a : b)
#define max(a, b) (a > b ? a : b)

typedef long long int ll;
#define r() fast_read()

int is_digit(const char c) {
  return c >= 48 and c <= 57;
}

ll fast_read(void) {
  ll n = 0, sign = 1;
  char c = getchar();
  while (not is_digit(c)) {
    if (c == '-') sign = ~0;
    c = getchar();
  }
  while (is_digit(c)) {
    n = (n << 1) + (n << 3) + (c ^ 48);
    c = getchar();
  }
  return sign * n;
}

#define MAX_N 1010

typedef struct TreeNode {
  int val;
  struct TreeNode *left;
  struct TreeNode *right;
} TreeNode;

int n, pre[MAX_N], vals[MAX_N], valsSize;

TreeNode *insertIntoBST(TreeNode* root, int* val) {
  if (root == NULL) {
    root = malloc(sizeof *root);
    root->val   = *val;
    root->left  = NULL;
    root->right = NULL;
    return root;
  }
  if (*val < root->val)
    root->left = insertIntoBST(root->left, val);
  else
    root->right = insertIntoBST(root->right, val);

  return root;
}

void preOrder(TreeNode *root) {
  if (root == NULL) return;
  *(vals + valsSize++) = root->val;
  preOrder(root->left);
  preOrder(root->right); 
}

void postOrder(TreeNode *root) {
  if (root == NULL) return;
  postOrder(root->left);
  postOrder(root->right);
  printf("%d ", root->val);
}

TreeNode *invert(TreeNode *root) {
  if (root == NULL) return root;
  root->left = invert(root->left);
  root->right = invert(root->right);
  TreeNode* tmp = root->left;
  root->left= root->right;
  root->right = tmp;
  return root;
}

int check(void) {
  rep(i, 0, n) if (*(vals + i) != *(pre + i)) return 0;
  return 1;
}

signed main(int argc, char const *argv[]) {
  // freopen("test.in", "r", stdin);

  n = r();
  TreeNode *root = NULL;
  rep(i, 0, n) {
   *(pre + i) = r();
   root = insertIntoBST(root, pre + i);
  }

  preOrder(root);
  if (check())
    return puts("YES"), postOrder(root), ~~(1 ^ 1);

  root = invert(root);
  valsSize = 0;
  preOrder(root);
  if (check())
    return puts("YES"), postOrder(root), ~~(1 ^ 1);

  // fclose(stdin);
  return puts("NO"), ~~(0 ^ 0);
}

感觉很麻烦的一道题！

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {};
  TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {};
  TreeNode(int _val, TreeNode* _left, TreeNode* _right) : val(_val), left(_left), right(_right) {};
  ~TreeNode() {};
};

int n;

TreeNode* construct1(vector<int>& preorder, vector<int>& inorder, int i, int j, int n)  {
  if (n <= 0) return (TreeNode*) nullptr;
  if (n == 1) return new TreeNode(preorder[i]);

  int k = j;
  while (k < j + n && inorder[k] != preorder[i]) ++k;
  if (k == j + n) return (TreeNode*) nullptr;
  const int l = k - j; // l == 左子树的长度 ...

  auto root = new TreeNode(inorder[k]);
  root->left  = construct1(preorder, inorder, i + 1, j, l);
  root->right = construct1(preorder, inorder, i + 1 + l, k + 1, n - l - 1);

  return root;
}

TreeNode* construct2(vector<int>& preorder, vector<int>& inorder, int i, int j, int n)  {
  if (n <= 0) return (TreeNode*) nullptr;
  if (n == 1) return new TreeNode(preorder[i]);

  int k = j + n - 1;
  while (k >= j && inorder[k] != preorder[i]) --k;
  if (k < j) return (TreeNode*) nullptr;
  const int l = k - j; // l == 左子树的长度 ...

  auto root = new TreeNode(inorder[k]);
  root->left  = construct2(preorder, inorder, i + 1, j, l);
  root->right = construct2(preorder, inorder, i + 1 + l, k + 1, n - l - 1);

  return root;
}

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
  return construct1(preorder, inorder, 0, 0, preorder.size());
}

TreeNode* buildTree2(vector<int>& preorder, vector<int>& inorder) {
  return construct2(preorder, inorder, 0, 0, preorder.size());
}

void inOrder(TreeNode* root, vector<int>& vals) {
  if (!root) return;
  inOrder(root->left, vals);
  vals.emplace_back(root->val);
  inOrder(root->right, vals);
}

void postOrder(TreeNode* root, vector<int>& ans) {
  if (!root) return;
  postOrder(root->left, ans);
  postOrder(root->right, ans);
  ans.emplace_back(root->val);
}

void printAns(vector<int>& ans) {
  for (int i = 0; i < ans.size(); ++i) {
    printf("%d", ans[i]);
    if (i < ans.size() - 1) printf(" ");
  }
  printf("\n");
}

int main(void) {
  cin >> n;
  vector<int> preorder(n);
  for (int i = 0; i < n; ++i) cin >> preorder[i];

  vector<int> inorder(preorder);
  sort(begin(inorder), end(inorder));

  auto root = buildTree(preorder, inorder);
  vector<int> v;
  inOrder(root, v);
  if (v == inorder) {
    puts("YES");
    vector<int> ans;
    postOrder(root, ans);
    printAns(ans);
  } else {
    sort(rbegin(inorder), rend(inorder));
    root = buildTree2(preorder, inorder);
    v.clear();
    inOrder(root, v);
    if (v == inorder) {
      puts("YES");
      vector<int> ans;
      postOrder(root, ans);
      printAns(ans);
    } else {
      puts("NO");
    }
  }
}