题目描述

有一棵二叉树，每个节点由一个大写字母标识(最多26个节点）。现有两组字母，分别表示前序遍历（父节点->左孩子->右孩子）和中序遍历（左孩子->父节点->右孩子）的结果，请你输出后序遍历（左孩子->右孩子->父节点）的结果。

解答要求时间限制：1000ms, 内存限制：100MB

输入

每个输入文件包含两串字母，各占一行。（每串只包含大写字母）
第一行字母表示前序遍历结果，第二行字母表示中序遍历结果。

输出

输出仅一行，表示后序遍历的结果，结尾换行。

样例

输入样例 1 

DBACEGF
ABCDEFG

输出样例 1

ACBFGED

提示样例 1

 

提示

前序遍历：根—>左孩子—>右孩子
中序遍历：左孩子—>根—>右孩子
后序遍历：左孩子—>右孩子—>根
所谓的前中后指的是根的位置，而左右孩子顺序是不变的。

例如已知前序遍历是DBACEGF，中序遍历是ABCDEFG，那么由前序遍历先根，可知道D是树的根，再看在中序遍历中D左边是ABC，所以可知道ABC一定在D的左子树上，而EFG在D的右子树上。
那么前序遍历为BAC,中序遍历为ABC，所以B为根，在中序遍历中A在B的左边，C在B的右边，所以A为B的左孩子，C为B的右孩子。

一、问题分析

首先读题，仔细看描述中的内容，发现需求是

1.有一颗二叉树，每个节点由一个大写字母标识（最多26个节点）。

2.现有两组字母，分别表示前序遍历（父节点->左孩子->右孩子）和中序遍历（左孩子->父节点->右孩子）的结果，请你输出后序遍历（左孩子->右孩子->父节点）的结果

3.输入：每个输入文件包含两串字母，各占一行。（每串只包含大写字母）

第一行字母表示前序遍历结果，第二行字母表示中序遍历结果。

4.输出：输出仅一行，表示后序遍历的结果，结尾换行。

5.提示：

前序遍历：根-》左孩子-》右孩子

中序遍历：左孩子-》根-》右孩子

后序遍历：左孩子-》右孩子-》根

例如已知前序遍历是DBACEGF，中序遍历是ABCDEFG，那么由前序遍历先根，可知道D是树的根，再看在中序遍历中D左边是ABC，所以可以知道ABC一定在D的左子树上，而EFG在D的右子树上。

那么前序遍历为BAC，中序遍历为ABC，所以B为根，在中序遍历中A在B的左边，C在B的右边，所以A为B的左孩子，C为B的右孩子。

6.思路：先从先序遍历中找到根节点，然后从中序遍历中找到左子树和右子树，递归，构建二叉树，最后进行后序遍历。

二、解题思路

1.首先接受前序遍历char preOrder[28];

scanf("%s", preOrder);

2.然后接受中序遍历char inOrder[28];

scanf("%s", inOrder);

3.我们需要定义树结构

typedef struct TreeNode {

struct TreeNode *left;

struct TreeNode *right;

char val;

}TreeNode;

4.还需要写一个可以递归构建二叉树的函数

TreeNode *constructTree(char* pre, char* in, int pre_start, int pre_end, int in_start, int in_end) {

// 如果传入的字符数为0，那么证明这是一个空节点

if(pre_end - pre_start) {

 return NULL;

}

// 如果传入的字符只有一个的话我们建立一个以这个字符为值的树节点，它的左右子树都是空

TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));

root->val = pre[pre_start];

root->left = NULL;

root->right = NULL;

int root_index_in_inorder = -1;

for(int i = in_start; i <= in_end; i++) {

if(in[i] == pre[pre_start]) {

root_index_in_inorder = i;

break;

}

}

int leftLen = root_index_in_inorder - in_start;

// 因为前序遍历先遍历根节点，根据这个可以知道前序遍历的根节点是第一个字符

// 在中序遍历中所有在根左边的都是根的左子树，所有在根右边的都是根的右子树

root->left = constructTree(pre, in, pre_start + 1, pre_start + leftLen, in_start, root_index_in_inorder - 1);

root->right =constructTree(pre, in, pre_start + leftLen + 1, pre_end, root_index_in_inorder + 1, in_end);

return root;

}

三、具体步骤

使用的语言是C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// 定义二叉树节点结构体
typedef struct TreeNode {
    struct TreeNode* left;
    struct TreeNode* right;
    char val;
} TreeNode;

// 根据前序和中序遍历序列构建二叉树
TreeNode* constructTree(char* pre, char* in, int pre_start, int pre_end, int in_start, int in_end) {
    if (pre_start > pre_end) {
        return NULL;
    }
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = pre[pre_start];
    root->left = NULL;
    root->right = NULL;

    int root_index_in_inorder = -1;
    for (int i = in_start; i <= in_end; i++) {
        if (in[i] == pre[pre_start]) {
            root_index_in_inorder = i;
            break;
        }
    }
    int leftLen = root_index_in_inorder - in_start;
    root->left = constructTree(pre, in, pre_start + 1, pre_start + leftLen, in_start, root_index_in_inorder - 1);
    root->right = constructTree(pre, in, pre_start + leftLen + 1, pre_end, root_index_in_inorder + 1, in_end);
    return root;
}

// 后序遍历二叉树并输出节点值
void lastOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    lastOrder(root->left);
    lastOrder(root->right);
    printf("%c", root->val);
}

// 释放二叉树内存空间，采用后序遍历顺序释放
void freeTree(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

int main() {
    char preOrder[28];
    scanf("%s", preOrder);
    char inOrder[28];
    scanf("%s", inOrder);

    int preLen = strlen(preOrder);
    int inLen = strlen(inOrder);
    TreeNode* root = constructTree(preOrder, inOrder, 0, preLen - 1, 0, inLen - 1);
    lastOrder(root);
    printf("\n");
    freeTree(root);

    return 0;
}