hdu1710 Binary Tree Traversals

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1710

题意：给前序、中序求后序，多组

前序：根左右

中序：左右根

分析：因为前序（根左右）最先出现的总是根结点，所以令root为前序中当前的根结点下标（并且同时把一棵树分为左子树和右子树）。start为当前需要打印的子树在中序中的最左边的下标，end为当前需要打印的子树在中序中最右边的下标。递归打印这棵树的后序，递归出口为start > end。i为root所表示的值在中序中的下标，所以i即是分隔中序中对应root结点的左子树和右子树的下标。

#include<bits/stdc++.h>

using namespace std;

int n,pre[],in[],flag;

void post(int root,int start,int end)

{

    if(start>end)return;

    int i=start;

    while(i<=end&&in[i]!=pre[root])i++;

    post(root+,start,i-);

    post(root++i-start,i+,end);

    if(flag==)printf("%d",pre[root]),flag=;

    else printf(" %d",pre[root]);

}

int main()

{

    while(cin>>n)

    {

        flag=;

        for(int i=;i<n;i++)cin>>pre[i];

        for(int i=;i<n;i++)cin>>in[i];

        post(,,n-);

        cout<<endl;

    }

    return ;

}

巴特西

hdu1710 Binary Tree Traversals

最新文章

热门文章