博客

根据中序和后序，还原这颗二叉树，再前序遍历得到前序序列
抓定义：中序是“左中右”，后序是“左右中”
后序序列的最后一个元素即为根节点，在中序序列中找到这个元素，同时也就知道左右子树的元素个数了，在后序序列中左右子树的元素个数也是一样，此时就得到左右子树的中序和后序序列了，就递归了！🌹
(下面举个例子：)

#include <bits/stdc++.h>
using namespace std;

char* in = (char *)malloc(sizeof(char));
char* post = (char *)malloc(sizeof(char));

struct node
{
    char data;
    node *left, *right;
};

// 参数分别为后序序列最左下标、最右下标、中序序列最左下标、最右下标
node *create(int postL, int postR, int inL, int inR) 
{
    if (postL > postR)
        return NULL;
    node *root = new node;        // 创建根节点
    root->data = post[postR];     // 后序序列的最后一个元素是根节点
    
    int k;
    for (k = inL; k < inR; k++)   // 根据这个根节点将中序序列一分为二
        if (in[k] == post[postR])
            break;
    int num = k - inL;            // 左子树元素个数 = 根节点在中序序列里的下标 - 中序序列最左下标

    // printf("create( %d, %d, %d, %d );\n",postL, postL + num - 1, inL, k - 1);
    // printf("create( %d, %d, %d, %d );\n\n",postL + num, postR - 1, k + 1, inR);
    root->left = create(postL, postL + num - 1, inL, k - 1);  // 创建左子树
    root->right = create(postL + num, postR - 1, k + 1, inR); // 创建右子树

    return root;
}

void preOrder(node *root)
{
    if (root == NULL)
        return;
    cout << root->data;
    preOrder(root->left);
    preOrder(root->right);
}

int main()
{
    scanf("%s", in);   // 中序序列
    scanf("%s", post); // 后序序列
    int len = strlen(in);
    node *root = create(0, len - 1, 0, len - 1); // 创建一颗二叉树
    preOrder(root);    // 前序遍历
    return 0;
}

运行结果：