Post

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

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

题设

问题描述

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

输入形式

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

输出形式

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

样例输入

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

样例输出

1
7 4 2 8 9 5 6 3 1

题解

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#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;
}
This post is licensed under CC BY 4.0 by the author.