阅读751 返回首页    go 阿里云 go 技术社区[云栖]

【Tsinghua】树重建(Rebuild)

这道题就是各种顺序的遍历一棵树。。。

树重建(Rebuild)

描述

某二叉树的n个节点已经用[1, n]内的整数进行了编号。现给定该二叉树的中序遍历序列和后序遍历序列，试输出其对应的先序遍历序列。  

输入

第一行为一个整数n。

第二、三行，即已知的中序、后序遍历序列。

输出

仅一行。

若所给的中序、后序遍历序列的确对应于某棵二叉树，则输出其先序遍历序列。否则，输出-1。

输入样例1 

5
4 2 5 1 3
4 5 2 3 1

输出样例1 

1 2 4 5 3

输入样例2 

3
2 3 1
1 2 3

输出样例2 

-1

限制

1 ≤ n ≤ 5000

时间：2 sec

空间：256MB

输入和输出的遍历序列均为[1, n]内整数的一个排列，整数间均以空格分隔，行末没有多余空格。

提示

不同遍历序列中根节点的位置。



AC的代码：

#include <stdio.h>
#include <stdlib.h>
#define MAXN 5005


int in[MAXN];       //中序
int af[MAXN];       //后序
int ans[MAXN];		//最后输出的前序序列
int count=0;

struct TreeNode
{
    struct TreeNode* left;
    struct TreeNode* right;
    int elem;
};


TreeNode* BinTree(int inorder[], int aftorder[], int length)
{
	if(length == 0)
    {
        return NULL;
    }

    TreeNode* node = new TreeNode;		//新建一个树节点
    node->elem = *(aftorder+length-1);

	ans[count++]=node->elem;		//存入答案

    int rootIndex=0;

    for( ;rootIndex<length;rootIndex++)		//在中序遍历中找这个根节点
    {
        if(inorder[rootIndex]==*(aftorder+length-1))
            break;
    }
	if(rootIndex>=length)
	{
		printf("-1\n");
		exit(0);
	}

    node->left = BinTree(inorder,aftorder,rootIndex);
    node->right = BinTree(inorder+rootIndex+1 , aftorder+rootIndex , length-(rootIndex+1));

	return node;
}

int main()
{
	int n;
	scanf("%d",&n);

	int i;
	for(i=0;i<n;i++)
		scanf("%d",&in[i]);

	for(i=0;i<n;i++)
		scanf("%d",&af[i]);

    BinTree(in,af,n);

	for(i=0;i<count-1;i++)
		printf("%d ",ans[i]);
	printf("%d\n",ans[i]);

    return 0;
}




最后更新：2017-04-03 05:39:38

  上一篇：go Firefox无法同步问题的解决
  下一篇：go UILabel设置多种字体、颜色