閱讀751 返回首頁    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設置多種字體、顏色