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

阿豪boy

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

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

### 阿豪boy

【编程题目】重建二叉树（C++实现）

qq_28869927 ⋅ 2017/03/17 ⋅ 0

wwlcsdn000 ⋅ 01/16 ⋅ 0

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

z956281507 ⋅ 2017/12/13 ⋅ 0

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

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

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

BravoZu ⋅ 2014/02/27 ⋅ 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 实现原理

Weex起步

lilugirl ⋅ 56分钟前 ⋅ 0

Jenkins实践1 之安装

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

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

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

Jake_xun ⋅ 今天 ⋅ 0

Kylin 对维度表的的要求

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

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

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 ......