华为机试（根据中序遍历和后序遍历的结果构造二叉树）

二叉树每个节点由一个大写字母标识(最多26个节点)。现在有两组字母，分别表示后序遍历(左孩子->右孩子->父节点)和中序遍历(左孩子->父节点->右孩子)的结果，请输出层次遍历(逐层遍历)的结果。

输入描述：

输入为两个字符串，分别是二叉树后序和中序遍历的结果

输出描述：

输出二叉树的层次遍历结果

示例1：

输入

CBEFDA CBAEDF

输出

ABDCEF

————————————————

#include<stdio.h>

#include<malloc.h>

#include<stdlib.h>

#include<string.h>

typedef struct tree

{

char value;

tree*left;

tree*right;

};

//中序遍历和后序遍历的结果

char*end;

char*mid;

void createTree(tree*node, char *mid, char *end)

{

int count = strlen(end);

if (count <= 0)

{

node->left =nullptr;

node->right = NULL;

return;

}

node->value = end[count-1];

int valueIndex = 0;

//在中序遍历的结果里找到值为end[count]的元素，返回下标

for (int i = 0; i < count; i++)

{

char a = mid[i];

char b = end[count - 1];

if (a == b)

{

valueIndex = i;

break;

}

}

//（生成）判断左右树大小，当前节点是否还有子树

char*leftmid = (char*)malloc(sizeof(char)*(valueIndex + 1));

char*leftend = (char*)malloc(sizeof(char)*(valueIndex + 1));

memset(leftmid, '\0', count + 1);

memset(leftend, '\0', count + 1);

memcpy(leftmid, mid, valueIndex);

memcpy(leftend, end, valueIndex);

char*rightmid = (char*)malloc(sizeof(char)*(count - valueIndex));

char*rightend = (char*)malloc(sizeof(char)*(count - valueIndex-1));

memset(rightmid, '\0', count - valueIndex);

memset(rightend, '\0', count - valueIndex);

memcpy(rightmid, &mid[valueIndex+1], count - valueIndex-1);

memcpy(rightend, &end[valueIndex], count - valueIndex-1);

node->left = (tree*)malloc(sizeof(tree));

node->right = (tree*)malloc(sizeof(tree));

createTree(node->left, leftmid, leftend);

createTree(node->right, rightmid, rightend);

}

int main()

{

char a[] = { '4', '2', '6', '5', '3', '1','\0'};

end = a;

char b[] = { '2', '4', '1', '6','5', '3', '\0' };

mid = b;

tree root = { 1, NULL, NULL };

createTree(&root, mid, end);

return 0;

}