后序：3, 4, 2, 6, 5, 1（左右根） 
中序：3, 2, 4, 1, 6, 5（左根右） 
 

分析：后序序列的最后一位就是树的根节点，在中序序列中找到该根节点，则根节点的左右部分即为左右子树

后序：(3 4 2) (6 5) 1
中序：(3 2 4) 1 (6 5)

 找到第一个根节点，接着重复该过程，拆分后序序列的第一部分即左子树

后序：(3 4) 2

中序：(3)2(4) 

所以左子树的根节点是 2，其左右孩子为 3 和 4；

右子树同理：

后序：(6) 5

中序：(6) 5

右子树的根节点为5，左孩子为 6；

画出树形结构图：

         1

      /     \

    2        5

  /  \      /

3      4  6

先序序列为 ：(1, 2, 3, 4, 5, 6) (根左右)

那么将上述过程转化为代码：        文章引用

因为后序的最后一个总是根结点，令i在中序中找到该根结点，则i把中序分为两部分，左边是左子树，右边是右子树。因为是输出先序（根左右），所以先打印出当前根结点，然后打印左子树，再打印右子树。左子树在后序中的根结点为root – (end – i + 1)，即为当前根结点-右子树的个数。左子树在中序中的起始点start为start，末尾end点为i – 1.右子树的根结点为当前根结点的前一个结点root – 1，右子树的起始点start为i+1，末尾end点为end。

 

#include<iostream>
using namespace std;
 
int post[]={3,4,2,6,5,1};
int mid[]={3,2,4,1,6,5};
 
void pre(int root, int start, int end)	      //当前树的根节点  在后序序列中的起始位置  结束位置
{
    if(start>end) 
		return ;
    int i=start;
    while(i<end&&mid[i]!=post[root]) 	      //寻找中序序列中根节点的位置
		i++;
    printf("%d ", post[root]);
    pre(root-1-end+i,start,i-1);	      //查询左子树
    pre(root-1,i+1,end);		      //查询右子树
}

int main() 
{
    pre(5,0,5);
    return 0;
}