根据前序遍历和中序遍历构造二叉树

对于一个二叉树，如果我们我们知道他的前序遍历和中序遍历，那就可以直接构造还原出完整的二叉树。

举例：现在有一个二叉树，前序遍历是ABDECFG，中序遍历是DBEACGF。如何确定这个树的形态？

首先前序遍历的第一个字母是根，所以确定A是根，而在中序遍历里，我们找到了A的下标为3，把中序遍历分成xxxAxxx两部分，所以A的左子树大小为3.右子树大小也是3。回到前序遍历，从A往后属3个就是左子树的前序遍历，再往后数3个就是右子树的前序遍历。

这样我们就构造出第一个点。以preOrder[1..3]作为新的前序，inOrder[0..2]作为新的中序，就可以构造出A的左子树（右也同理）。

直到一个子树只剩下一个点，我们就构造完成了。

这样来看，我们会把整个树里的每个点都走一次，而每次如何查找前序的第一个点在中序里的下标呢？每次查找要遍历一遍，太慢了。可以开一个哈希表，每次直接查询节点对应的下标，这样总时间就是O(N)的。

struct node{
    node *ls, *rs;
    char name;
    node():name(0), ls(0), rs(0) {}
}*root(new node);

string preOrder, inOrder;
unordered_map<char, int> map_inOrder;

// generate的含义是，取 preOrder[l0..r0] 为前序，inOrder[l1..r1] 为中序构造一个 p 上的子树
void generate(int l0, int r0, int l1, int r1, node* p) {
    if (l0 > r0) return; // 已经到头了，不再往下构造
    p->name = preOrder[l0]; // 前序的第一个点 就是当前根节点

    int pos = map_inOrder[p->name]; 
    generate(l0+1, pos-l1+l0, l1, pos-1, p->ls=new node); 
    // 左子树的的中序从 l1 开始，pos-1结束，长度为 pos-l1, 所以计算出左子树的前序遍历从 l0+1 到 pos-l1+l0

    generate(pos-l1+l0+1, r0, pos+1, r1, p->rs=new node); // 右子树同理
}

main() {
    cin >> preOrder >> inOrder;
    int len = preOrder.size();

    for (int i=0; i<len; i++) map_inOrder[inOrder[i]] = i; //此处记录每个节点在中序遍历的下标
    generate(0, len-1, 0, len-1, root); // 左闭右闭
}

那么给定一个树的前序遍历和后序遍历，能不能构造出这个树呢？一般是不行的，反例很好找。就拿上面那个树来说，已知前序ABDECFG，后序DEBGFCA, 上面的树是一个答案，把 G 放到 F 的右边又是一个答案，一个前序遍历和一个后序遍历可以对应很多二叉树。