根据中序遍历结果和前序（后序）遍历结果重构二叉树

问题描述：

给出一棵二叉树的先序（或后序）遍历结果，以及中序遍历结果，如何构造这棵树

首先，我们需要回顾二叉树的三种遍历方式：

前序遍历：根+左子树+右子树
中序遍历：左子树+根+右子树
后序遍历：左子树+右子树+根

假设，当前二叉树的前序遍历结果为{1,2,4,5,3,6},中序遍历结果为{4,2,5,1,3,6}

1. 前序遍历的第一个元素，必然是树根，此处为1。

2. 根据“1”在中序出现的位置，将中序遍历的结果分成左右两棵子树，它们的中序遍历分别是：{4,2,5} 和{3,6}；这两棵子树的前序结果：{2,4,5}和{3,6}。
3. 现在我们重复步骤1、2，构造左子树

4. 现在我们重复步骤1、2，构造右子树

5. 合并树节点得到最终结果：

结合以上步骤，我们可以总结出如下规律：

1.根据前序（后序也适用）遍历结果，找到树根，设为ROOT，并生成一个以ROOT为根节点，左右子树
都为NULL的树

2.根据ROOT在中序遍历中的索引，将中序遍历结果分为：左子树，右子树；同时我们也要明确左右子树
对应的前序（后序）遍历结果

3.递归的执行步骤1和2即可构造出唯一的二叉树。

代码如下：

// 由前序序列和中序序列构造二叉树
#include <stdio.h>
#include <stdlib.h>

typedef struct BiNode* BiTree;
BiTree createBiTree(BiTree tree, char pre[], char in[]);

/*************************************
    *二叉链表表示二叉树 
    *data : 节点数据
    *lchild : 左孩子 
    *rchild : 右孩子
**************************************/
typedef struct BiNode
{
    char data;
    struct BiNode * lchild;
    struct BiNode * rchild; 
};

/**************************************
    *由前序序列和中序序列建立二叉树的过程  
    *t为要建立的二叉树
    *pre为前序序列
    *in为中序序列
***************************************/
BiTree createBiTree(BiTree tree, char pre[], char in[])
{
    if (pre == NULL || in == NULL)
    {
        return NULL;
    }
    int index, l_in = 0, r_in = 0, l_pre = 0, r_pre = 0;
    //根
    char rootNode = pre[0];
    //根在中序序列中的位置  
    for (int i = 0; i < sizeof(in); i++)
    {
        if (rootNode == in[i])
        {
            index = i;
        }
    }
    char lchild_in[sizeof(in)];
    char rchild_in[sizeof(in)];
    //左孩子的中序序列
    for (int i = 0; i < index; i++)
    {
        lchild_in[l_in] = in[i];
        l_in++;
    }
    //右孩子的中序序列
    for (int i = index + 1; i < sizeof(in); i++)
    {
        rchild_in[r_in] = in[i];
        r_in++;
    }
    char lchild_pre[sizeof(pre)];
    char rchild_pre[sizeof(pre)];
    //左孩子的前序序列  
    for (int i = 1; i < l_in + 1; i++)
    {
        lchild_pre[l_pre] = pre[i];
        l_pre++;
    }
    //右孩子的前序序列
    for (int i = l_in + 1; i < sizeof(pre); i++)
    {
        rchild_pre[r_pre] = pre[i];
        r_pre++;
    }

    tree = (BiTree)malloc(sizeof(BiNode));
    if (tree != NULL)
    {
        tree->data = rootNode;
        //递归创建左孩子
        createBiTree(tree->lchild, lchild_pre, lchild_in); 
        //递归创建右孩子 
        createBiTree(tree->rchild, rchild_pre, rchild_in); 
    }
}

参考：

1. 根据中序遍历结果和前序（后序）遍历结果重构二叉树
2. 根据前序遍历序列和中序遍历序列构造二叉树算法