NOIP普及2001，求先序排列数据结构与算法Sakuracode的博客-

【二叉树】求先序排列

传送门：求先序排列

  给定二叉树先序和中序求后序，和给定后序和中序求先序的问题是关于二叉树最基础的问题（蒟蒻刚刚学树)，这三种遍历方法的不同与根节点的遍历顺序有关，都可以用递归实现：
  先序根遍历：先访问根节点，然后用先序根遍历访问左子树，最后用先序根遍历访问右子树
  中序根遍历：先用中序根遍历访问左子树，然后访问根节点，最后用中序根遍历访问右子树
  后续根遍历：先用后续根遍历访问左子树，然后用后序根遍历访问右子树，最后访问根节点
  这三种遍历方式是二叉树内容的基础的基础。这里不再赘述

  我们看回这道题，因为后序遍历的特性，后序遍历序列的最后一个节点就是这棵二叉树的根，知道根了以后，再来看中序遍历，因为中序遍历是先访问左子树，再是根，最后是右子树的，所以中序遍历序列以后序遍历序列的最后一个节点为界限，左侧的就是左子树的中序遍历序列，右边的就是右子树的中序遍历序列。那么怎么求出左子树和右子树的后序遍历序列呢？用中序序列我们可以求出左子树和右子树的节点数（也就是序列长度），然后后序序列的左侧是左子树，右边是右子树，那么我们知道长度，把后序序列的起始坐标加上左子树长度，这一段就是左子树的后序序列。然后就是先输出根，然后看左子树和右子树的长度，不是空就递归去输出它们（所以根本用不着建树？）
  可能有点绕，但只要明白后序遍历的最后一个是根节点，在中序遍历找到根节点的位置，其左侧就是左子树，右侧是右子树。其它的就都是细节问题了~。

  贴出开始那道题的AC代码：

#include<iostream> #include<cstdio> #include<cstring> using namespace std; char in[10],post[10]; int lena,lenb; void f(int,int,int,int); int main(){  ios::sync_with_stdio(false);  cin>>in>>post;  lena=strlen(in);  lenb=strlen(post); f(0,lena-1,0,lenb-1); return 0; } void f(int lin,int rin,int lpost,int rpost){ //找到根输出（即后序根遍历的最后一个）   cout<<post[rpost]; //在中序根序列找到根节点，其左边的就是该节点的左子树 int idx; for(int i=lin;i<=rin;i++){ if(in[i]==post[rpost]){    idx=i; break; } } //如果非空，输出左子树 if(idx-1 >= lin){ f(lin,idx-1,lpost,lpost+(idx-1-lin)); } //如果非空，输出右子树 if(idx+1 <= rin){ f(idx+1,rin,lpost+(idx-1-lin)+1,rpost-1); } } 

（AC不易，各位大佬不点个赞吗？）