HDU1710 - 由先序和中序遍历生成后序遍历

题设

问题描述

由二叉树的先序序列和中序序列构造二叉树并求其后序序列

输入形式

每个测试用例的第一行包含一个整数n（1<=n<=1000）表示二叉树的节点个数，所有节点的编号为1~n，后面两行分别给出先序序列和中序序列。可以假设构造出的二叉树是唯一的。

输出形式

对于每个测试用例，输出一行表示其后序序列。

样例输入

9
1 2 4 7 3 5 8 9 6
4 7 2 1 8 5 9 3 6

样例输出

7 4 2 8 9 5 6 3 1

题解

首先读入先序遍历和中序遍历，然后遵循以下规则递归：先序遍历的第一个数一定是根节点，在中序遍历中查找这个数，这个数的左边就是左子树的中序遍历，右边就是右子树的中序遍历。而偏移量的大小p就是左子树的大小，那么从先序遍历的根节点往后p位就是左子树的先序遍历，其余的是右子树的先序遍历，分别递归即可。递归时可以跨过建树，直接得到后序遍历。

#include <iostream>
using namespace std;
const int N = 1010;

int pre[N], in[N], ans[N];
int n;

void solve(int n, int* s1, int* s2, int* s) {
  if (n <= 0) return;
  int p;
  for (int i = 0;; i++) {
    if (s2[i] == s1[0]) {
      p = i;
      break;
    }
  }
  s[n - 1] = s1[0];
  solve(p, s1 + 1, s2, s);
  solve(n - p - 1, s1 + p + 1, s2 + p + 1, s + p);
}

int main() {
  // freopen("in.txt", "r", stdin);
  cin >> n;
  for (int i = 0; i < n; i++) cin >> pre[i];
  for (int i = 0; i < n; i++) cin >> in[i];
  solve(n, pre, in, ans);
  for (int i = 0; i < n; i++) printf("%d ", ans[i]);
  puts("");
  return 0;
}