PAT A1119 前序遍历后续遍历不唯一生成

£神魔★判官ぃ 2022-03-07 04:16 90阅读 0赞

clipboard.png

之前仅仅接触过如何通过二叉树的中序+先序/后序序列生成唯一二叉树,这一次见到了这个新的题型;

这里先梳理一个概念,之所以会生成树不唯一,一定是有一个叶子,无论其在父节点的左右子节点,都可能生成相同的先序和后序遍历序列;

所以这个时候,思路就很清晰,我们判别一个序列是否唯一,条件就是是否有一个节点只有一个子节点;

大致的序列分割和先序和后续相同,这个后面专门开一个blog进行总结;

  1. #include<iostream>
  2. #include<stdlib.h>
  3. #include<stdio.h>
  4. #include<vector>
  5. #include<set>
  6. #include<algorithm>
  7. using namespace std;
  8. using std::vector;
  9. using std::set;
  10. vector<int>in,pre,post;
  11. bool uniq=true;
  12. void chargement(int prl,int prr,int pol,int por){
  13. if(prl==prr){
  14. in.push_back(pre[prl]);
  15. return ;
  16. }
  17. if(pre[prl]==post[por]){
  18. int i=prl+1;
  19. while(i<=prr&&pre[i]!=post[por-1])
  20. i++;
  21. if(i-prl>1)
  22. chargement(prl+1,i-1,pol,pol+(i-prl-1)-1);
  23. else
  24. uniq=false;
  25. in.push_back(post[por]);
  26. chargement(i,prr,pol+(i-prl-1),por-1);
  27. }
  28. }
  29. int main(){
  30. int n;
  31. scanf("%d",&n);
  32. pre.resize(n);
  33. post.resize(n);
  34. for(int i=0;i<n;i++)
  35. scanf("%d",&pre[i]);
  36. for(int i=0;i<n;i++)
  37. scanf("%d",&post[i]);
  38. chargement(0,n-1,0,n-1);
  39. printf("%s\n%d", uniq == true ? "Yes" : "No", in[0]);
  40. for (int i = 1; i < in.size(); i++)
  41. printf(" %d", in[i]);
  42. printf("\n");
  43. system("pause");
  44. return 0;
  45. }

发表评论

表情:
评论列表 (有 0 条评论,90人围观)

还没有评论,来说两句吧...

相关阅读