L2-006. 树的遍历

已知二叉树的后序遍历和中序遍历，求出它的层序遍历

与前两个不同的是，层序遍历必须先建立一个树，然后BFS，就是广度优先搜索，不懂的话可以看【这篇文章】

由于树的节点只能用指针指向，所以建立指针数组，再遍历就OK了。

/* 7 2 3 1 5 7 6 4 1 2 3 4 5 6 7 * 4 1 6 3 5 7 2 */
#include<iostream>
#include<cstring>
#include<cstdlib>
typedef struct node
{
    struct node *left;
    struct node *right;
    int data;
}Node;
using namespace std;
Node *binarytree(int a[],int b[],int len)
{
    int i;
    if (len==0)
    return NULL;
    Node *tree;
    tree=(Node *)malloc(sizeof(Node));
    tree->data=a[len-1];
    for (i=0;i<len;i++)
    {
        if (b[i]==a[len-1])
        break;
    }
    tree->left=binarytree(a,b,i);
    tree->right=binarytree(a+i,b+i+1,len-i-1);
    return tree;
}
int main()
{
    int n;
    cin>>n;
    int mid[n],next[n];
    for (int i=0;i<n;i++)
    cin>>next[i];
    for (int i=0;i<n;i++)
    cin>>mid[i];
    Node *que[n];
    int head=0,tail=0;
    que[tail++]=binarytree(next,mid,n);
    while (head<tail)
    {
        cout<<que[head]->data;
        if (head!=n-1)
        cout<<" ";
        if (que[head]->left!=NULL)
        que[tail++]=que[head]->left;
        if (que[head]->right!=NULL)
        que[tail++]=que[head]->right;
        head++;
    }
}