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

42次阅读

共计 831 个字符,预计需要花费 3 分钟才能阅读完成。

题目粗心:

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

算法思路:

这里采纳不建树然而借鉴建树的过程,后序遍历第一个结点实际上是左子树最左的结点,咱们只须要一直递归拜访左子树,直到第一次遇到最左的结点即可,这里应用变量 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;
} 

正文完
 0