由前序和中序遍历序列重建二叉树
由前序和中序遍历序列重建二叉树
阿豪boy 发表于11个月前
由前序和中序遍历序列重建二叉树
  • 发表于 11个月前
  • 阅读 2
  • 收藏 0
  • 点赞 0
  • 评论 0

标题:腾讯云 新注册用户域名抢购1元起>>>   

http://acm.nyist.net/JudgeOnline/problem.php?pid=221

输入

The input will contain one or more test cases. 
Each test case consists of one line containing two strings preord and inord, representing the preorder traversal and inorder traversal of a binary tree. Both strings consist of unique capital letters. (Thus they are not longer than 26 characters.) 
Input is terminated by end of file.

输出

For each test case, recover Valentine's binary tree and print one line containing the tree's postorder traversal (left subtree, right subtree, root).

样例输入

DBACEGF ABCDEFG
BCAD CBAD

样例输出

ACBFGED
CDAB

 

我的代码

#include <iostream>
#include <string.h>
#include <cstdio>
using namespace std;

struct Node{
	char c;
	Node *left,*right;
	Node(char c):c(c){
		left=NULL;
		right=NULL;
	} 
}; 
char in[30],pre[30],post[30]; 

//由 in[a-b] pre[c-d] 建树 返回根节点 
Node* createByInPre(int a,int b,int c,int d){
	if (a>b) return NULL;		//空区间 
	Node *node = new Node(pre[c]) ;	//新节点的值为根节点的值
	int k;	//在中序序列中找到in[k] = pre[c]的节点
	for(k=a;k<=b && in[k]!=pre[c];k++); 
	int numleft = k-a;	//左子树节点个数
	node->left = createByInPre(a,k-1,c+1,d+numleft);
	node->right=createByInPre(k+1,b,c+numleft+1,d);
	return node; 
} 

void postOrder(Node* root){
	if(!root) return;
	postOrder(root->left);
	postOrder(root->right); 
	printf("%c",root->c); 
}

int main(int argc, char *argv[])
{
	Node* root; 
	while(scanf("%s %s",pre,in)!=EOF ){
		int len=strlen(in);
		root = createByInPre(0,len-1,0,len-1);
		postOrder(root);
		printf("\n");
	}	
	return 0;
}

 

题目推荐

 
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

void build(int n,const char* s1,const char* s2,char* s)
{
  if(n<=0) return ;
  int p=strchr(s2,s1[0])-s2;
  build(p,s1+1,s2,s);
  build(n-p-1,s1+p+1,s2+p+1,s+p);
  s[n-1]=s1[0];
}
int main()
{
  char s1[30],s2[30],s[30];
  while(scanf("%s %s",s1,s2)!=EOF)
  {
    int n=strlen(s1);
    build(n,s1,s2,s);
    s[n]='\0';
    printf("%s\n",s);
  }
  return 0;
}
        

 

共有 人打赏支持
粉丝 5
博文 507
码字总数 386453
×
阿豪boy
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: