PAT1138 Postorder Traversal（树的遍历）

题意：

给定一棵书的先序遍历和后序遍历，然后找出这棵树后序遍历的第一个元素

思路:

这题的思路很简单，考虑到只要输出第一个元素，所以若有左子树就递归左子树，如果没有左子树，才找右子树。但这题有个点很怪，都是同样的方法我的代码就超时，找了网上别人写的有的能过有的不能过，下面是一个能过的。我看了一下好像PAT是支持#include <bits/stdc++.h>的，下次可以直接用。

#include <bits/stdc++.h>
using namespace std;
const int MAX=5*1e4+5;
int pre[MAX],in[MAX];//存储先根序列，中根序列
//寻找后根遍历第一个数
void findNode(int root,int left,int right){if(left==right){//如果是叶节点printf("%d",pre[root]);//这个数就是我们要找的数，输出这个数return ;}//在中根序列中寻找与根节点的位置int i=left;while(in[i]!=pre[root])++i;if(i==left)//如果没有左子树findNode(root+1,i+1,right);//向右子树中寻找else//如果有左子树findNode(root+1,left,i-1);//向左子树中寻找
}
int main()
{int N;scanf("%d",&N);for(int i=0;i<N;++i){scanf("%d",&pre[i]);}for(int i=0;i<N;++i){scanf("%d",&in[i]);}findNode(0,0,N-1);return 0;
}