# 11111: 【原1111】二哥学二叉树

### 题目描述

author: Cheng Chen 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1111

## Sample Input

``````ABCD
``````

## Sample Output

``````A B C NULL NULL D
``````

## FineArtz's solution

``````/* 二哥学二叉树 */
#include <iostream>
#include <cstring>
using namespace std;

char a[1005];
char dlr[30], ldr[30];

void restoreTree(char *dlr, char *ldr, int len, int root){
if (len <= 0)
return;
char r = dlr[0];
a[root] = r;
int i = 0;
while (ldr[i] != r)
++i;
restoreTree(dlr + 1, ldr, i, root * 2);
restoreTree(dlr + i + 1, ldr + i + 1, len - i - 1, root * 2 + 1);
}

int main(){
cin >> dlr >> ldr;
for (int i = 1; i <= 1004; ++i)
a[i] = ' ';
restoreTree(dlr, ldr, strlen(dlr), 1);
int n = 1000;
while (a[n] == ' ')
--n;
for (int i = 1; i <= n; ++i){
if (a[i] == ' ')
cout << "NULL ";
else
cout << a[i] << ' ';
}
cout << endl;
return 0;
}
``````

## ligongzzz's solution

``````#include "iostream"
#include "cmath"
#include "cstring"
using namespace std;

//二叉树类
template <class T>
class myBinaryTree {
public:
class node {
public:
T data;
T *lchild=nullptr, *rchild=nullptr;
};
node *root=nullptr;

//清空
void clear() {
clear(root);
}

void clear(node *p) {
if (p == nullptr)
return;
clear(p->lchild);
clear(p->rchild);
delete p;
p = nullptr;
}

//构造
myBinaryTree(){}

//析构
~myBinaryTree() {
clear(root);
}

//判断是否非空
bool empty() {
return root == nullptr;
}
};

char tdata[1009] = { 0 };
int dataSize = 0;

void createTree(int rootNum, char *tempData1,char *tempData2) {
if (strlen(tempData1) == 0) return;
char root = tempData1[0];
tdata[rootNum] = root;
dataSize = rootNum < dataSize ? dataSize : rootNum;
char ldata1[50] = { 0 }, rdata1[50] = { 0 }, ldata2[50] = { 0 }, rdata2[50] = { 0 };
int length = strlen(tempData1);
bool flag = false;
for (int i = 0,k=0; i < length; i++,k++) {
if (tempData2[i] == root) {
flag = true;
k = -1;
}
else if (!flag) {
ldata1[k] = tempData1[i + 1];
ldata2[k] = tempData2[i];
}
else if (flag) {
rdata1[k] = tempData1[i];
rdata2[k] = tempData2[i];
}
}
//递归
createTree(rootNum * 2, ldata1, ldata2);
createTree(rootNum * 2 + 1, rdata1, rdata2);
}

int main() {
char preData[50], postData[50];
cin >> preData >> postData;

createTree(1, preData, postData);

//输出
cout << tdata[1];
for (int i = 2; i <= dataSize; i++) {
if (tdata[i] == 0)
cout << " NULL";
else
cout << " " << tdata[i];
}

return 0;
}
``````

## Neight99's solution

``````#include <cstring>
#include <iostream>

using namespace std;

char tree[100000] = {0}, Left[100000], Middle[100000];

char* subString(char* str, int l, int r) {
if (r < l) {
return NULL;
}
char* tmp = new char[100000];
for (int i = l; i <= r; i++) {
tmp[i - l] = str[i];
}

tmp[r + 1] = 0;

return tmp;
}

void createTree(char* strLeft, char* strMiddle, int n) {
int i = 0, j = 0;
char *lltmp, *lmtmp, *rltmp, *rmtmp;
if (strLeft == NULL) {
return;
}

tree[n] = strLeft[0];

if (strlen(strLeft) == 1 || strlen(strMiddle) == 1) {
return;
}

for (i = 0; i < strlen(strMiddle); i++) {
if (strMiddle[i] == strLeft[0]) {
break;
}
}
j = (i + 1 > strlen(strLeft)) ? (strlen(strLeft) - 1) : (i + 1);

lltmp = subString(strLeft, 1, j - 1);
lmtmp = subString(strMiddle, 0, i - 1);
rltmp = subString(strLeft, j, strlen(strLeft) - 1);
rmtmp = subString(strMiddle, i + 1, strlen(strMiddle) - 1);

createTree(lltmp, lmtmp, 2 * n);
createTree(rltmp, rmtmp, 2 * n + 1);

delete[] lltmp;
delete[] lmtmp;
delete[] rltmp;
delete[] rmtmp;
}

int main() {
int i, j = 1, k = 0;
cin >> Left >> Middle;
i = strlen(Left);
createTree(Left, Middle, 1);
for (; k < i;) {
if (tree[j] < 'A' || tree[j] > 'Z') {
cout << "NULL ";
j++;
} else {
cout << tree[j] << " ";
j++;
k++;
}
}

return 0;
}
``````

## WashSwang's solution

``````#include <iostream>
#include <cstring>
using namespace std;
char pre[100],in[100],ans[2000];
int maxn;
void dfs(int ps,int pe,int is,int it,int p)
{
int root,leftlen,rightlen;
for (root=is;root<it;++root){
if (in[root]==pre[ps])
break;
}
ans[p]=in[root];
if (p>maxn) maxn=p;
leftlen=root-is;
if (leftlen>0) dfs(ps+1,ps+leftlen,is,root,p*2);
rightlen=it-root-1;
if (rightlen>0) dfs(ps+leftlen+1,pe,root+1,it,p*2+1);
}
int main() {
cin>>pre;
cin>>in;
dfs(0,strlen(pre),0,strlen(in),1);
for (int i=1;i<=maxn;++i)
if (ans[i]) cout<<ans[i]<<" ";
else cout<<"NULL ";
return 0;
}
``````

## yyong119's solution

``````#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

char pre[27], mid[27];
char treeData[1001];

void buildTree(char *pstart, char *mstart, int len, int pos) {
if (len > 0) {
treeData[pos] = *pstart;
int i;
for (i = 0; i < len; ++i)
if (mstart[i] == *pstart) break;
buildTree(pstart + 1, mstart, i, pos * 2);
buildTree(pstart + 1 + i, mstart + i + 1, len - i - 1, pos * 2 + 1);
}
}

int main() {
cin >> pre >> mid;
int n = strlen(pre);
buildTree(pre, mid, n, 1);
int cnt = 0;
for (int i = 1; i <= 1000 && cnt < n; ++i)
if (treeData[i] != '\0') {
cout << treeData[i] << " ";
++cnt;
}
else cout << "NULL ";
return 0;
}
``````

## Zsi-r's solution

``````#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

void f(int root , int start ,int end,int count,char tree[],const char pre[],const char mid[]){
int i;
if (end < start)
return;
else
tree[count] = pre[root];

for (i = start; i <= end;i++)
if (mid[i]==pre[root])
break;
f(root + 1, start, i - 1, 2 * count, tree, pre, mid);
f(root + 1 + i - start, i + 1, end, 2 * count + 1, tree, pre, mid);
}

int main()
{
char pre[27], mid[27];
char tree[1001];

cin >> pre;
cin >> mid;
int len = strlen(pre);
for (int k = 0; k<1000 ;k++)
{
tree[k] = '@';
}

f(0, 0, len - 1, 1, tree, pre, mid);

int num = 0, i = 1;
while (num!=len)
{
if (tree[i]=='@')
cout << "NULL" << ' ';
else{
cout << tree[i] << ' ';
num++;
}
i++;
}

return 0;
}
``````