PAT甲級1020（附帶前中序周遊の絕對幹貨）

引子

我之前對周遊推導這塊沒怎麼動腦子，憑感覺。是以這題是先參考了百度經驗，别笑，這個連結，我覺得講得非常清楚。

https://jingyan.baidu.com/article/cdddd41cb8d79753ca00e144.html

讀懂它的前提是，你靜下心來，而不是像找規律一樣，似是而非地懂了。那樣毫無卵用。

通過推導它再舉一反三推導其他題，你發現，思路是：

先通過後序的特點，找總的根節點。然後确定總根的右節點，一般是postorder最後一個節點（總根）的前一個節點post[4]=5。然後通過結合後序中序中相同的數字，如65，56确定好它們在一個最小子樹中的位置，逐漸完善總根的右子樹。然後找總根的左節點。一般是postorder中從後往前把右子樹的節點數光的第一個節點。

則從PostOrder看，左子樹的根節點序号為root的序号（比如0~5的5）-右子樹節點的個數（2）-1=2。左子樹根節點為post[2]=2~

int post[] = {3, 4, 2, 6, 5, 1};

int in[] = {3, 2, 4, 1, 6, 5};

很多文章說是root-(end-i+1)。但我比較能了解我自己的式子。當然它式子的end-i，這裡的end是InOrder最後一位的序号，i是InOrder的根節點，相減是右子樹節點數沒錯。

下面是根據上述數組推導前序的代碼：

#include<cstdio>
using namespace std;
int post[] = {, , , , , };
int in[] = {, , , , , };
void pre(int root,int start,int end){
    if(start>end) return;
    int i=start;//找到根節點在InOrder中序号
    while(i<end&&in[i]!=post[root]) i++;
     printf("%d",post[root]);//列印根節點
     pre(root-(end-i)-,start,i-);//左根節點從postorder角度看，i-1從inorder角度看
     pre(root-,i+,end);//右根節點從postorder角度看，i+1從inorder角度看
}
int main(){
    pre(,,);
    return ;
}
           

正文

1020 Tree Traversals (25)（25 分）

Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the level order traversal sequence of the corresponding binary tree.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=30), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the level order traversal sequence of the corresponding binary tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:

7

2 3 1 5 7 6 4

1 2 3 4 5 6 7

Sample Output:

4 1 6 3 5 7 2

這題沒啥頭緒，先學習柳婼大神的

https://www.liuchuo.net/archives/2100

#include<iostream>
#include<vector>
using namespace std;
vector<int> post,in,level(,-);
void pre(int root,int start,int end,int index){
    if(start>end) return;
    int i=start;//找到根節點在InOrder中序号
    while(i<end&&in[i]!=post[root])i++;
    // printf("%d",post[root]);//列印根節點
     level[index]=post[root];
     pre(root-(end-i)-,start,i-,*index+);//左根節點從postorder角度看，i-1從inorder角度看
     pre(root-,i+,end,*index+);//右根節點從postorder角度看，i+1從inorder角度看
}

int main(){
  int n,cnt=;
  cin>>n;
  post.resize(n);
  in.resize(n);
  for(int i=;i<n;i++){
    scanf("%d",&post[i]);

  }

  for(int i=;i<n;i++){
    scanf("%d",&in[i]);

  }
  pre(n-,,n-,);
  for(int i=;i<level.size();i++){
    if(level[i]!=-){
      if(cnt!=) cout<<" ";
      cout<<level[i];
      cnt++;
    }
    if(cnt==n)break;
  }
  return ;
}
           

//有機會帶來自己的了解。