二叉树输入前序和中序怎么输出后序.c

这是一个二叉树遍历的问题。如果已知二叉树的前序遍历和中序遍历，可以通过递归的方式构造出该二叉树并输出后序遍历。

具体步骤如下：

1. 根据前序遍历确定二叉树的根节点；
2. 在中序遍历中找到根节点的位置，根节点左侧的部分即为左子树的中序遍历，右侧的部分即为右子树的中序遍历；
3. 根据左子树的中序遍历和左子树的前序遍历递归构造左子树；
4. 根据右子树的中序遍历和右子树的前序遍历递归构造右子树；
5. 后序遍历即为左子树后序遍历 + 右子树后序遍历 + 根节点。

具体代码实现如下：

#include<iostream>
using namespace std;
const int N=505;
int pre[N],in[N],post[N],n;
void build(int il,int ir,int pl,int pr,int &k)
{
    if(il>ir) return;
    int root=pre[pl],mid;
    for(int i=il;i<=ir;i++)
        if(root==in[i])
        {
            mid=i;
            break;
        }
    build(il,mid-1,pl+1,pl+mid-il,&k);
    build(mid+1,ir,pl+mid-il+1,pr,&k);
    post[k++]=root;
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>pre[i];
    for(int i=0;i<n;i++)
        cin>>in[i];
    int k=0;
    build(0,n-1,0,n-1,k);
    for(int i=0;i<n;i++)
        cout<<post[i]<<" ";
    cout<<endl;
    return 0;
}

该算法的时间复杂度为O(n^2)，因为每次构建二叉树时需要在中序遍历中查找根节点的位置，可以通过使用哈希表优化到O(n)。