【二叉树】求先序排列

传送门：求先序排列

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

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

  贴出开始那道题的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不易，各位大佬不点个赞吗？）