HDU 1710Binary Tree Traversals(已知前序中序，求后序的二叉树遍历)

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

解题思路：可以由先序和中序的性质得到 ： 先序的第一个借点肯定是当前子树的根结点， 那么在

中序中找到这个结点， 则这个结点左边的节点属于左子树， 右边的属于右子树。然后递归遍历就可以了。

样例:

9

1 2 4 7 3 5 8 9 6

4 7 2 1 8 5 9 3 6

 

7 4 2 8 9 5 6 3 1

如图：

 

因此，用深搜就能轻松解决了，注意DFS中的变量，以及向清楚DFS的条件，这题就简单多了，具体看代码吧：

#include<iostream>

#include<string.h>

#include<cstdio>

#include<stack>

using namespace std;

#define maxn 1001

int m,n,a[maxn],b[maxn];  //先序数组和后序数组

stack<int>Q;            //存放父节点

void dfs(int l1,int r1,int l2,int r2)

{//l1,r1,是先序遍历的数组的开始和末尾，l2,r2是中序遍历的数组的开始和末尾

    int i,j;

    Q.push(a[l1]);  //父节点入栈

    for(i=l2;i<=r2;i++)

        if(b[i]==a[l1])  break;

   //i 父节点在中序遍历的位置,j 左子树和右子树在先序遍历的分界点，即右子树的父节点

        j=l1+(i-l2+);

        if(j<=r1&&i-<=r2)     dfs(j,r1,i+,r2);  //求解右子树

        if(l1+<=j-&&l2<=i-)  dfs(l1+,j-,l2,i-);  //求解左子树

//不能换位置，根据输出的后序遍历图可以看出，栈的后方为右半部分

}

int main()

{

    while(cin>>n)

    {

        for(int i=;i<n;i++)  scanf("%d",&a[i]);

        for(int i=;i<n;i++)  scanf("%d",&b[i]);

        dfs(,n-,,n-);

        while(!Q.empty())

        {

            printf("%d",Q.top());

            Q.pop();

            if(Q.size())  printf(" ");

        }

        cout<<endl;

    }

    return ;

}