关于算法-数据结构:PAT甲级1138-Postorder-Traversal

题目粗心：

给定一颗二叉树的前序和中序遍历序列，输入后序遍历序列的第一个数字

算法思路：

这里采纳不建树然而借鉴建树的过程，后序遍历第一个结点实际上是左子树最左的结点，咱们只须要一直递归拜访左子树，直到第一次遇到最左的结点即可，这里应用变量 c 来管制是否是第一次拜访，初始为 0，在 c ==0&&preL==preR 阐明是第一次达到最左的结点，那么就输入以后结点并且 ++c。

留神点：

• 1、测试的工夫在测试点 4 时而高时而低，无奈通过的多提交几次。

提交后果：

AC 代码：

#include<cstdio>
#include<vector>

using namespace std;

struct Node{
    int data;
    Node *left;
    Node *right;
};

int N;
vector<int> pre,in,post;

int c=0; 
void createTree(int preL,int preR,int inL,int inR){if(preL>preR||c!=0) return ;
    int k;// 中序序列中根节点的地位 
    for(k=inL;k<=inR;++k){if(pre[preL]==in[k]) break;
    }
    int numOfLeft = k-inL;
    createTree(preL+1,preL+numOfLeft,inL,k-1);
    createTree(preL+numOfLeft+1,preR,k+1,inR);
    if(c==0&&preL==preR){printf("%d",pre[preL]);
        ++c;
        return;
    }
    return ;
}

int main(){scanf("%d",&N);
    for(int i=0;i<N;++i){
        int a;
        scanf("%d",&a);
        pre.push_back(a);
    }
    for(int i=0;i<N;++i){
        int a;
        scanf("%d",&a);
        in.push_back(a);
    }
    createTree(0,N-1,0,N-1);
    return 0;
}