通过先序和中序数组生成后序数组

[编程题]通过先序和中序数组生成后序数组

热度指数：2792 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出一棵二叉树的先序和中序数组，通过这两个数组直接生成正确的后序数组。

输入描述:

第一行一个整数 n，表示二叉树的大小。

第二行 n 个整数 a_i，表示二叉树的先序遍历数组。

第三行 n 个整数 b_i，表示二叉树的中序遍历数组。

输出描述:

输出一行 n 个整数表示二叉树的后序遍历数组。

示例1

输入

3
1 2 3
2 1 3

输出

2 3 1

备注:


数据保证合法

算法知识视频讲解

查看答案及解析

勇敢牛牛，不怕困难！

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

typedef struct {
  int val;
  int l_child, r_child;
} TreeNodeInfo, *INFO;

TreeNodeInfo infos[10010]; // 全局区

int createTree(int* pre, int* inorder, int i, int j, int n) {
  // recursion exit condition
  if (n <= 0) return 0;
  if (n == 1) return *(pre + i);

  int k = j;
  while (*(inorder + k) != *(pre + i)) ++k;
  int l = k - j;
  
  infos[*(pre + i)].l_child = createTree(pre, inorder, i + 1, j, l);
  infos[*(pre + i)].r_child = createTree(pre, inorder, i + 1 + l, k + 1, n - 1 - l);
  return *(pre + i);
}

void postorder(INFO infos, int index) {
  if (!index) return;
  postorder(infos, infos[index].l_child);
  postorder(infos, infos[index].r_child);
  fprintf(stdout, "%d ", index);
}

int main(int argc, char* argv[]) {
  int n;
  fscanf(stdin, "%d", &n);
  
  int i, pre[n], inorder[n];
  for (i = 0; i < n; ++i) fscanf(stdin, "%d", pre + i);
  for (i = 0; i < n; ++i) fscanf(stdin, "%d", inorder + i);
  
  createTree(pre, inorder, 0, 0, n);
  postorder(infos, *pre);
  return 0;
}

发表于 2021-08-03 19:21:10 回复(0)