二叉树后序+中序序列求前序序列

题目描述

后序+中序序列构造二叉树。

输入描述

第一行输入序列长度n，第二行输入n个字符表示二叉树后序遍历的序列，第三行输入n个字符表示二叉树中序遍历的序列。

输出描述

输出二叉树先序遍历的序列。

示例

输入

9
GHDBEIFCA
GDHBAECIF

输出

ABDGHCEFI

分析

前序：根-左-右
中序：左-根-右
后序：左-右-根

利用后序得到根节点，再通过中序查找根节点划分左右子树，递归的重复这个过程就可以得到二叉树。

提前对序列进行预处理可以将整个过程的时间复杂度降为O(n)，详见代码。

AC代码

---

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

int n;
string in, po;
unordered_map<char, int> mp;  //预处理，降低时间复杂度

void build(string& in, string& po, int root, int l, int r)
{
    /* l，r为中序的范围
     * root为该中序范围对应二叉树的根节点在后序序列的下标 */
    if(l > r)
        return;
    int idx = mp[po[root]];
    cout << in[idx];
    build(in, po, root - r + idx - 1, l, idx - 1);
    /* 利用后序的性质来确定左子树的根节点的下标
     * 即用根节点在后序中的索引减去右子树的长度得到左子树的根 */
    build(in, po, root - 1, idx + 1, r);
    /* 右子树的根显然就是root-1了 */
}

int main()
{
    cin >> n >> po >> in;
    for(int i = 0; i < n; i++)  //预处理
        mp[in[i]] = i;
    build(in, po, po.size() - 1, 0, po.size() - 1);
    return 0;
}