HDU - 1710 Binary Tree Traversals （二叉树前中序得到后序）

本文主要是介绍HDU - 1710 Binary Tree Traversals （二叉树前中序得到后序），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

给定前中序得到后序序列。

Input

第一行包含一个n(1<=n<=1000)表示有n个节点，后两行为前序和后序序列。

Output

输出后序序列。

Sample Input

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

Sample Output

7 4 2 8 9 5 6 3 1

Solution

由前中、后中得到其他序列的板题。

#include <iostream>
#include <cstdio>
#include <vector>
#define N 1005
using namespace std;
vector<int> V;           //存放父节点
int pre[N], in[N]; //先序数组和后序数组
void make(int preleft, int preright, int inleft, int inright)
{int parent, leftsize, rightsize;for (parent = inleft; parent <= inright; parent++)if (in[parent] == pre[preleft])break; //找到父节点在中序遍历的位置parentleftsize = parent - inleft;rightsize = inright - parent; //获得左树和右树的大小if (leftsize > 0)make(preleft + 1, preleft + leftsize, inleft, parent - 1); //如果有左子树,递归重建左子树if (rightsize > 0)make(preleft + leftsize + 1, preright, parent + 1, inright); //如果有右子树,递归重建右子树//父节点入栈，如果在连个if中间则为中序遍历，之前则为前序遍历V.push_back(in[parent]);
}
int main()
{int i, n, num;// freopen("in.txt", "r", stdin);while (scanf("%d", &n) != EOF){// 清空向量，注意empty一定要声明为局部变量，否则交换两次后empty便不为空vector<int> empty;swap(V, empty);for (i = 0; i < n; i++)scanf("%d", &pre[i]);for (i = 0; i < n; i++)scanf("%d", &in[i]);  //输入make(0, n - 1, 0, n - 1); //建树for (int i = 0; i < V.size(); i++){printf("%d%c", V[i], i != V.size() - 1 ? ' ' : '\n');}}return 0;
}

这篇关于HDU - 1710 Binary Tree Traversals （二叉树前中序得到后序）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---