1138 Postorder Traversal

Topic: give the sequence of sequenced sequence of two binary tree and output the first value of subsequent sequence.

Train of thought: at first glance, it is not a pre order + middle order reconstruction of the two binary tree, and then the traversal of it. There is no mistake in doing so, but it does not really comprehend the intention of the subject. The problem is not to let us output the posterior sequence, but to output the first value of the ordinal sequence. Taking into account the order of traversal traversal is left sub tree -Gt; right subtree – & gt; root node, think about it, if the root node has left subtree, then the first value of the sequence must be in the left subtree, then the right subtree is not our concern; if there is no left subtree, then the first value of the sequence is in the right subtree. Therefore, we only needYou can recursively find this value in a regular “build binary tree” function, without actually rebuilding the binary tree. The amount of code is much less.

Code:

#include <cstdio>
const int maxn=50005;
int pre[maxn],in[maxn];
int n;
int func(int preL,int preR,int inL,int inR)
{
    if(preL==preR) return pre[preL];//boundaryint pos=inL;
    while(in[pos]!=pre[preL]) pos++;
    int leftCnt=pos-inL;//The number of nodes of the left subtreeif(leftCnt>0) return func(preL+1,preL+leftCnt,inL,pos-1);//If left sub tree exists, recursive to left subtree.else return func(preL+1,preR,pos+1,inR);//The left child tree does not exist, and the right subtree recurs.
}

int main()
{
    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]);
    printf("%d",func(0,n-1,0,n-1));
    return 0;
}