[数据结构与算法]二叉树中已知中序遍历和先序遍历（后序遍历），求后序遍历（先序遍历）（C++）

?前言：

? ? ? ? ?某些地方描述上可能不太严谨~

?????????l代表left，r代表right

? ? ? ? ?begin_find,middle_find,end_find分别代表先序遍历，中序遍历，后序遍历

1. 已知中序遍历和后序遍历，求先序遍历：

? ? ? ? 先序遍历的访问顺序是根，左子树，右子树，所以思路比较简单，先利用后序遍历找到根root输出，然后从中序遍历里找到root下左（右）子树的元素，从这些元素里找到下一层的根去输出，直到所有元素都输出。

? ? ? ? 总的来说就是一个递归的过程，不断的寻找根去输出，从第一层到最后一层。

#include<bits/stdc++.h>
using namespace std;
string middle_find,end_find;
void begin_find(int middle_l, int middle_r, int end_l, int end_r)
{
    if(middle_l > middle_r) return;
    //后序遍历的最后一个元素即为根
    char root = end_find[end_r];
    printf("%c", root);
    //pos记录根在中序遍历中的位置
    //中序遍历中pos左(右)边的是左(右)子树中的元素
    int pos = 0;
    while(middle_find[pos] != root) pos++;
    //cnt为中序遍历中root前面的元素个数
    int cnt = pos - middle_l;
    //找出root下左子树的根
    begin_find(middle_l, pos-1, end_l, end_l + cnt - 1);
    //找出root下右子树的根
    begin_find(pos+1, middle_r, end_l + cnt, end_r - 1);
}
int main(void)
{
    cin >>middle_find >> end_find;
    int len = middle_find.length() - 1;
    begin_find(0, len, 0, len);
    return 0;
}

1. 已知中序遍历和先序遍历，求后序遍历：

? ? ? ? 后序遍历的访问顺序是左子树，右子树，根，大体思路和前面是一样的，但是因为根是在最后的，所以递归写出的程序应该是先递归root下的左子树，再递归root下的右子树，最后输出根

#include<bits/stdc++.h>
using namespace std;
string begin_find,middle_find;
void end_find(int begin_l, int begin_r, int middle_l, int middle_r)
{
    if(begin_l > begin_r) return;
    //先序遍历的第一个元素即为根
    char root = begin_find[begin_l];
    //pos记录根在中序遍历中的位置
    //中序遍历中pos左(右)边的是root下左(右)子树中的元素
    int pos = 0;
    while(middle_find[pos] != root) pos++;
    //cnt为中序遍历中root前面的元素个数
    int cnt = pos - middle_l;
    //递归root下的左子树
    end_find(begin_l + 1, begin_l + cnt, middle_l, pos - 1);
    //递归root下的右子树
    end_find(begin_l + cnt + 1, begin_r, pos + 1, middle_r);
    //输出根
    cout <<root;
}
int main(void)
{
    cin >>begin_find >> middle_find;
    int len = begin_find.length() - 1;
    end_find(0, len, 0, len);
    return 0;
}

?后续可能会加上二叉树的四种遍历方式说明，看情况