已知中序遍历和先序遍历求后序遍历

zxzmnh 2019-09-22 原文

已知中序遍历和先序遍历求后序遍历

给一棵树的先序遍历和中序遍历如下：

先序遍历：ABCDEFGHI

后序遍历：CEDFBAHGI

后序遍历结果：EFDCBHIGA

首，先序遍历的过程为根-左-右，中序遍历的过程为左-根-中，后序遍历的过程为左-右-根

由先序遍历过程可知先序遍历最开始的都是根，所以可以由先序遍历的根对应中序遍历中的根从而在中序遍历中对树进行划分。

划分结果

先序遍历的根：

A B C D E F G H I

下面是递归求解的过程，过程中注意每一个子区间代表一课子树，在判断子树根的位置时要考虑这棵子树是否有左子树或者右子树，对没有的情况要特判

#include<stdio.h>
#include<cstring>
#pragma warning(disable:4996)
#define maxn 100000
using namespace std;
char s1[maxn];
char s2[maxn];
void dfs(char root, int pos, int l, int r)
{
    if (r - l <= 1)
    {
        if(root != ' ')
        printf("%c", root);
        return;
    }
    for (int i = l; i < r; i++)
    {
        if (s2[i] == root)
        {
            char t = pos + 1 < strlen(s1)&&i !=l ? s1[pos + 1] : ' ';//i == l 没有左子树
            dfs(t, pos + 1, l, i);
            t = pos + 1 + i - l < strlen(s1)&&i!=r-1 ? s1[pos + 1 + i - l] : ' ';//i= r-1没有右子树
            dfs(t, pos + 1 + i - l, i+1, r);
            printf("%c", root);
        }
    }


}
int main()
{
    scanf("%s%s",s1,s2);
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    char root = s1[0];
    dfs(root, 0, 0, len2);
    getchar();
    getchar();
    return 0;
}