文档章节

由前序和中序遍历序列重建二叉树

 阿豪boy
发布于 2017/02/24 18:47
字数 399
阅读 3
收藏 0
点赞 0
评论 0

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;
}
        

 

© 著作权归作者所有

共有 人打赏支持
粉丝 21
博文 881
码字总数 631558
作品 0
西安
【编程题目】重建二叉树(C++实现)

题目描述:输入二叉树的前序遍历和中序遍历结果 ,请重建出该二叉树,返回其头节点并给出后序遍历序列。假设输入的遍历序列不包含重复数字。 题目分析: 根据前序遍历和中序遍历的特征,我们...

qq_28869927 ⋅ 2017/03/17 ⋅ 0

剑指Offer学习总结-重建二叉树

剑指Offer学习总结-重建二叉树 本系列为剑指Offer学习总结,主要是代码案例的分析和实现: 书籍链接:http://product.dangdang.com/24242724.html 原作者博客:http://zhedahht.blog.163.co...

wwlcsdn000 ⋅ 01/16 ⋅ 0

跟我一起学算法系列6---重建二叉树

1.题目描述 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,...

充电实践 ⋅ 2017/12/31 ⋅ 0

剑指Offer-根据二叉树的前序和后序遍历重建二叉树

原文地址:点击打开链接 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 例如输入前序遍历序列{1,2,4,7,3,5,6,8} 和...

z956281507 ⋅ 2017/12/13 ⋅ 0

重构二叉树之前序遍历和中序遍历

题目描述: 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 例如输入前序遍历序列{1,2,4,7,3,5,6,8} 和中序遍历序列{...

wall--e ⋅ 2016/04/26 ⋅ 0

【剑指Offer】重建二叉树——JavaScript实现

题目描述 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,...

highboys ⋅ 2017/11/27 ⋅ 0

二叉树相关题目

1、求二叉树深度 int GetDepth(BinaryTreeNode * pRoot){ if(pRoot == NULL) // 递归出口 return 0; int depthLeft = GetDepth(pRoot->m_pLeft); int depthRight = GetDepth(pRoot->m_pRigh......

ahucsxl ⋅ 2015/08/31 ⋅ 0

轻松搞定面试中的二叉树题目

二叉树节点定义如下: struct BinaryTreeNode{ int m_nValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight;}; 1. 求二叉树中的节点个数 递归解法: (1)如果二叉树为空,节点个数为...

BravoZu ⋅ 2014/02/27 ⋅ 0

轻松搞定面试中的二叉树题目

求二叉树中的节点个数 2. 求二叉树的深度 3. 前序遍历,中序遍历,后序遍历 4.分层遍历二叉树(按层次从上往下,从左往右) 5. 将二叉查找树变为有序的双向链表 6. 求二叉树第K层的节点个数 ...

亚特兰缇斯 ⋅ 2015/09/10 ⋅ 0

Lintcode7 Binary Tree Serialization solution 题解

【题目描述】 Design an algorithm and write code to serialize and deserialize a binary tree. Writing the tree to a file is called 'serialization' and reading back from the file t......

coderer ⋅ 2017/04/17 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

JavaScript零基础入门——(十)JavaScript的DOM基础

JavaScript零基础入门——(十)JavaScript的DOM基础 欢迎大家回到我们的JavaScript零基础入门,上一节课,我们了解了JavaScript中的函数,这一节课,我们来了解一下JavaScript的DOM。 第一节...

JandenMa ⋅ 37分钟前 ⋅ 0

Spring mvc DispatchServlet 实现原理

在Spring中, ContextLoaderListener只是辅助类,在web 容器启动的时候查找并创建WebApplicationContext对象,通过该对象进行加载spring的配置文件。而真正的逻辑实现其实是在DispatcherSer...

轨迹_ ⋅ 48分钟前 ⋅ 0

Weex起步

本教程假设你已经在你的本地环境安装了node 其实weex起步教程在 https://github.com/lilugirl/incubator-weex 项目说明文件中都已经有了,但为了有些同学看到英文秒变文盲,所以这里我重新写...

lilugirl ⋅ 56分钟前 ⋅ 0

Jenkins实践1 之安装

1 下载 http://mirrors.jenkins.io/war/latest/jenkins.war 2 启动 java -jar jenkins.war 前提:安装jdk并配置环境变量 启动结果节选: ************************************************......

晨猫 ⋅ 今天 ⋅ 0

组合数学 1-2000 中,能被6或10整除的数的个数

1--2000 中,能被6或10整除的数的个数 利用集合的性质 能被6整除的个数 2000/6 = 333 能被10整除的个数 2000/10 = 200 能被6和10整除的个数 2000/30 = 66 能被6或10整除的个数 333+200-66 =...

阿豪boy ⋅ 今天 ⋅ 0

一篇文章学懂Shell脚本

Shell脚本,就是利用Shell的命令解释的功能,对一个纯文本的文件进行解析,然后执行这些功能,也可以说Shell脚本就是一系列命令的集合。 Shell可以直接使用在win/Unix/Linux上面,并且可以调用...

Jake_xun ⋅ 今天 ⋅ 0

大数据工程师需要精通算法吗,要达到一个什么程度呢?

机器学习是人工智能的一个重要分支,而机器学习下最重要的就是算法,本文讲述归纳了入门级的几个机器学习算法,加大数据学习群:716581014一起加入AI技术大本营。 1、监督学习算法 这个算法由...

董黎明 ⋅ 今天 ⋅ 0

Kylin 对维度表的的要求

1.要具有数据一致性,主键值必须是唯一的;Kylin 会进行检查,如果有两行的主键值相同则会报错。 2.维度表越小越好,因为 Kylin 会将维度表加载到内存中供查询;过大的表不适合作为维度表,默...

无精疯 ⋅ 今天 ⋅ 0

58到家数据库30条军规解读

军规适用场景:并发量大、数据量大的互联网业务 军规:介绍内容 解读:讲解原因,解读比军规更重要 一、基础规范 (1)必须使用InnoDB存储引擎 解读:支持事务、行级锁、并发性能更好、CPU及...

kim_o ⋅ 今天 ⋅ 0

代码注释中顺序更改 文件读写换行

`package ssh; import com.xxx.common.log.LogFactory; import com.xxx.common.log.LoggerUtil; import org.apache.commons.lang3.StringUtils; import java.io.*; public class DirErgodic ......

林伟琨 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部