数据结构期末复习——还原二叉树（根据先序和中序遍历输出先序遍历）

#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
#include<algorithm>
#include<vector>
#include<cstring>
#include<sstream>
#include<cmath>
using namespace std;
const int maxn = 100000;
char pre[maxn];     /**先序遍历后对应的串*/
char ino[maxn];     /**中序遍历后对应的串*/
//char post[maxn];    /**后序遍历后对应的串*/
typedef struct BiNode
{
    char data;
    BiNode *Left;
    BiNode *Right;
}BiNode, *BiTree;

BiTree build(char *pre, char *ino, int len)
{
    if(len == 0)
        return NULL;
    BiTree T = new BiNode;
    T->data = *pre;
    char *root = pre;
    char *p = ino;
    while(p)
    {
        //找到根节点在中序中对应的位置
        if(*p == *root)
            break;
        ++p;
    }
    //左子树的长度
    int left_len = p - ino;
    T->Left = build(pre + 1, ino, left_len);
    T->Right = build(pre + 1 + left_len, p + 1, len - left_len - 1);
    return T;
}

//后序遍历
void postOrder(BiTree T)
{
    if(T)
    {
        postOrder(T->Left);
        postOrder(T->Right);
        printf(" %c", T->data);
    }
}


int main()
{
    /**N指二叉树节点的个数*/
    int N;
    scanf("%d %s %s", &N, pre, ino);
    BiTree T = build(pre, ino, N);
    printf("postorder:");
    postOrder(T);
    printf("\n");
}

参考博客：https://blog.csdn.net/qq_37708702/article/details/79644068