【第五周】3. 已知一个二叉树的中序遍历序列和后序遍历序列，求这

简书内代码已上传GitHub：点击我 去GitHub查看代码

数据结构学校OJ作业 --- 树相关

来张助于理解分治策略的图 分治策略 -- 来源网络

【问题描述】
已知一个二叉树的中序遍历序列和后序遍历序列，求这棵树的前序遍历序列。

【输入形式】
一个树的中序遍历序列 该树后序遍历序列，中间用空格分开。输入序列中仅含有小写字母,且没有重复的字母

【输出形式】
一个树的前序遍历序列

【样例输入】
dbeafcg debfgca

【样例输出】
abdecfg

思路：

• 这题的思路很清晰：读取中序和后序序列 、 利用分治策略递归解决问题。

• 至于怎么读取呢？前序中序...反正不管什么顺序，他们都是等长的，以空格分隔读取下来存在字符串里就好了。

• 分治的思路：因为后序遍历最后一个节点一定是根节点，所以利用确定的根节点在中序遍历中确认左右子树的位置，然后再分别对左右子树确定它们的左右子树，一直划分到不能再划分位置。

• 可以参考 二叉树刷题总结(三) 的105题，那题和这题是一样的，只要学会了分治思想怎么来其实都是一个样。

下面是代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
// 读取序列
void TravelToString(char* s1, char* s2){
    char c;
    // flag用于记录中序后序分界
    int flag = 1, i = 0;
    // max存储序列长度，用于结束读取
    int max = -1;
    while(i != max){
        scanf("%c", &c);
        // 读取完中序序列
        if(c == ' ') {
            flag = 0;
            // 串尾标记
            s1[i] = '\0';
            max = i;
            // 更新i
            i = 0;
            continue;
        }
        // 存储
        if(flag){
            s1[i++] = c;
        }else{
            s2[i++] = c;
        }
    }
    // 串尾标记
    s2[i] = '\0';
}
// 分治策略
void PrintPreorder(char* s1, int len1, char* s2, int len2){
    if(len1 == 0) return;
    // 获取根节点
    char root = s2[len2 - 1];
    printf("%c", root);
    // 寻找根节点在中序遍历中的位置
    int index = -1;
    while(s1[++index] != root);
    // 继续划分左右子树
    PrintPreorder(s1, index, s2, index);
    PrintPreorder(s1 + index + 1, len1 - index - 1, s2 + index, len1 - index - 1);
}
int main(){
    // 这就是我学校OJ水平， 太真实了~~
    char s1[20], s2[20];
    int len1, len2;
    // 读取 中序遍历、后序遍历序列
    TravelToString(s1, s2);
    len1 = strlen(s1);
    len2 = strlen(s2);
    
    // 分治
    PrintPreorder(s1, len1, s2, len2);
    
    return 0;
}

分治的时候要注意的就是 边界问题，传参的时候要仔细考虑考虑，避免出错~~

如果有看不懂的，私信我！！！
~_^^
每天进步一点，加油！

End

END