二叉樹-已知兩種周遊求第三種

1，先序和中序，輸出後序

#include<iostream>
#include<stack>
using namespace std;
const int N=1010;
int n,pre[N],in[N]; //先序數組和後序數組
stack<int> st;      //存放父節點
void build(int l1,int r1,int l2,int r2) //l1,r1,是先序數組，l2,r2中序數組
{   
    int i,j;
    st.push(pre[l1]);    //父節點入棧
    for(i=l2;i<=r2;i++)
        if(in[i]==pre[l1])  //找到父節點在中序周遊的位置i
            break;
    j=l1+(i-l2+1);      //确定左子樹和右子樹在先序周遊的分界點j，即右子樹的父節點
    if(j<=r1 && i+1<=r2)    //求解右子樹
        build(j,r1,i+1,r2);
    if(l1+1<=j-1 && l2<=i-1)    //求解左子樹
        build(l1+1,j-1,l2,i-1);
}

int main()
{
	cin>>n;
  	for(int i=0;i<n;i++)
        cin>>pre[i];
    for(int i=0;i<n;i++)
        cin>>in[i];
    build(0,n-1,0,n-1);
    while(!st.empty())
	{
        cout<<st.top()<<" ";   
        st.pop();
    }
    return 0;
}
           

2，後序和中序，輸出先序

#include<iostream>
#include<stack> 
using namespace std;
stack<int>p;
int bac[100],in[100];
void bfs(int l1,int r1,int l2,int r2)//l1,r1中序，l2,r2後序 
{
	cout<<bac[r2]<<" ";
	int i,j;
	for(i=l1;i<=r1;i++)
	{
		if(in[i]==bac[r2])
		break;
	} 
	j=r2-(r1-i+1);
	if(i-1>=l1&&j>=l2)
	bfs(l1,i-1,l2,j);//左子樹 
	if(r1>=i+1&&r2-1>=j+1)
	bfs(i+1,r1,j+1,r2-1);//右子樹 
}
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	cin>>bac[i];
	for(int i=0;i<n;i++)
	cin>>in[i];
	bfs(0,n-1,0,n-1);
} 
/*
8
4 6 5 2 8 7 3 1
4 2 6 5 1 8 3 7
*/