题目简介

给定二叉树T（树深度H<=10，深度从1开始，结点个数N<1024，结点编号1~N）的层次遍历序列和中序遍历序列，输出T从左向右叶子结点以及二叉树先序和后序遍历序列。

输入格式

输入共三行：第一行是整数n，表示二叉树中的结点数目；第二行有n个整数，表示该二叉树的层次遍历序列；第三行也是n个整数，表示该二叉树的中序遍历序列。整数间以空格隔开。

输出格式

输出三行，分别是：从左向右的叶子结点，先序遍历序列，后序遍历序列。结点编号用空格隔开。

样例输入

    7

3 5 4 2 6 7 1

2 5 3 6 4 7 1

样例输出

2 6 1

3 5 2 4 6 7 1

2 5 6 1 7 4 3

思路分析

二叉树的遍历问题 ，可以通过递归来求解。其中的关键就在于如何传递参数。主要面临如下问题

1.传什么参数

2.传参数的范围如何

　　对于中序遍历序列，传参的问题不难解决，首先判断一下根节点的位置，如果不在最右边，证明有左子树。把原区间从根节点位置一劈两半，得到新的子树的中序遍历的位置参数。右边同理

　　而这时候问题就在于，对于层序遍历序列，如何传参? 　　层序遍历序列的作用其实就是找出这棵树的根节点，对于原始树，我们很容易发现第一个节点就是根节点，但是对于子树来讲，我们该如何确定它的根节点是谁呢？答案就在层序遍历序列里，层序遍历是一层一层的，从上往下遍历的，也就是说父亲总是比儿子先遍历到，对于一个子树来讲，他的节点在层序遍历序列中的位置可能是不连续的，但是这些节点中，在层序遍历序列排在最前面的，就是这颗树的根节点。

　　我们先假定层序遍历的第1个节点就是这颗子树的根，然后去子树里面寻找，如果没找到，说明我们假定错了，虽然这个节点辈分很高，但是不在这个子树里面，于是我们假定第二个节点为这颗子树的根，在去子树里面寻找，以此类推，直到找到第一个，可以在子树里面找到的节点，这就是这个子树的根

　　有了根节点，我们就可以肆意妄为了，对于层序遍历序列，我们把整个序列都传下去，然后根据我们的需要选择输出根节点与遍历左右子树的先后关系即可。值得注意的是，题目还让输出叶子节点，只需要将任意一种遍历树的函数的输出语句加上l=r这样一句话，限定叶子节点即可。由于我们访问的顺序是先左后右，因此叶子们被访问的顺序也是从左至右的

#include<iostream>
#include<string>
using namespace std;
int n;
int lev1[100000];
int mid2[100000];

void tree0(int l1,int r1,int l2, int r2)
{
    
    int i=0,j=0;
    for( i=l1;i<=r1;i++)
    {
        int k=0;//打上标记，一会儿找到第一个满足条件的就直接退出 
        for(j =l2;j<=r2;j++)
        {
            if(mid2[j]==lev1[i])
            {
                k=1;
                break;
            }
        }
        if(k==1)
        break;
    }
    if(l2==r2)
        cout<<lev1[i]<<" ";
    if(j>l2)//own left tree
        tree0(l1,r1,l2,j-1);

    if(j<r2)//own right tree
        tree0(l1,r1,j+1,r2);
    return ;
}

void tree1(int l1,int r1,int l2, int r2)
{
    int i=0,j=0;
    for( i=l1;i<=r1;i++)
    {
        int k=0;
        for(j =l2;j<=r2;j++)
        {
            if(mid2[j]==lev1[i])
            {
                k=1;
                break;
            }
        }
        if(k==1)
        break;
    }
    //i is root loc in lev1
    cout<<lev1[i]<<" ";
    if(j>l2)//own left tree
        tree1(l1,r1,l2,j-1);

    if(j<r2)//own right tree
        tree1(l1,r1,j+1,r2);
    return ;
}

void tree2(int l1,int r1,int l2, int r2)
{
    int i=0,j=0;
    for( i=l1;i<=r1;i++)
    {
        int k=0;
        for(j =l2;j<=r2;j++)
        {
            if(mid2[j]==lev1[i])
            {
                k=1;
                break;
            }
        }
        if(k==1)
        break;
    }
    //i is root loc in lev1
    
    if(j>l2)//own left tree
        tree2(l1,r1,l2,j-1);

    if(j<r2)//own right tree
        tree2(l1,r1,j+1,r2);
    cout<<lev1[i]<<" ";
    return ;
}
int main()
{
    
    cin>>n;
    for(int i=0;i<n;i++)
    cin>>lev1[i];
    for(int i=0;i<n;i++)
    cin>>mid2[i];
    tree0(0,n-1,0,n-1);
    cout<<endl;
    tree1(0,n-1,0,n-1);
    cout<<endl;
    tree2(0,n-1,0,n-1);
    return 0;
}