【UVA 536】Tree Recovery 题解（根据遍历序列还原二叉树）

小瓦伦丁非常喜欢玩二叉树。她最喜欢的游戏是随机构建

查找节点中带有大写字母的二叉树。 这是她创作的一个例子：

为了给后代记录她的树，她为每棵树写下了两个字符串：预订单 遍历（根、左子树、右子树）和有序遍历（左子树、根、右子树。 对于上面绘制的树，预序遍历是DBACEGF，有序遍历是ABCDEFG。 她认为这样一对字符串将提供足够的信息，以便稍后重建树 （但她从未尝试过）。 现在，几年后，她再次看着琴弦，意识到重建树木确实是 这是可能的，但只是因为她从未在同一棵树上两次使用同一个字母。 然而，手工重建很快就变得乏味。 所以现在她让你写一个程序来帮她完成任务！

输入 输入文件将包含一个或多个测试用例。 每个测试用例由一行组成，其中包含两个字符串“preord”和“order”，表示 二叉树的预序遍历和有序遍历。这两个字符串都由唯一的大写字母组成。 （因此，它们不超过26个字符。） 输入在文件结束时终止。 输出 对于每个测试用例，恢复Valentine的二进制树，并打印一行包含树的postorder 遍历（左子树、右子树、根）。

Sample Input DBACEGF ABCDEFG BCAD CBAD Sample Output ACBFGED CDAB

思路

分别用两个数组存储先序遍历（pre）和中序遍历（mid）序列，先序遍历的第一个元素为根节点d，中序遍历以根节点d为界划分左右子树，中序遍历中查找根节点d，数组下标记为index。在还原二叉树的过程中输出后序遍历序列。

左子树先序遍历起点：pre + 1 左子树中序遍历起点：mid 左子树在数组中的长度：index 右子树先序遍历起点：post + index + 1 右子树中序遍历起点：mid + index + 1 右子树在数组中的长度：len - index - 1

AC代码

#include <iostream>
#include <cstring>
#define AUTHOR "HEX9CF"
using namespace std;

int len;
char pre[30], mid[30];

void restore(char *pre, char *mid, int len)
{
    if (0 == len)
    {
        return;
    }
    char d = pre[0];
    int index = 0;
    while (mid[index] != d)
    {
        index++;
    }
    restore(pre + 1, mid, index);
    restore(pre + index + 1, mid + index + 1, len - index - 1);
    cout << d;
}

int main()
{
    while (cin >> pre >> mid)
    {
        len = strlen(pre);
        restore(pre, mid, len);
        cout << endl;
    }
    return 0;
}