Pat grade a 1020 tree Traversals

The middle order traversal sequence of binary tree , And post order traversal sequence , Find sequence traversal sequence

Middle order traversal sequence ：[left, root, right], Post traversal sequence ：[left, right, root]

postorder: 4 5 2 3 1  inorder: 4 2 5 1 3

  First look at the following traversal sequence , The last one is root node 1, then inorder Can be 1 To the left and right   

obtain 4 2 5 and 3; Then according to the element ,postorder Can be reduced to 4 5 2 and 3.1 Deleted

take 1 Stored in a binary tree structure value, then postorder Turn into 2 A the ,inorder Also become a 2 A the

postorder1: 4 5 2   inorder1: 4 2 5

postorder2: 3     inorder2: 3

Then according to the subsequent traversal, the last 1 position , You can get the root node root1=2, then inorder1 By 2 Cut away , Continue to divide the left branch into two

postorder3: 4     inorder  4

postorder4: 5     inorder4: 5

The overall structure of the binary tree can be obtained recursively , Pay attention to the binary tree assignment in advance malloc Memory

#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<string>
#include<map>
#include<set>
#include<bits/stdc++.h>

using namespace std;
int x, y, z;

struct nodees{
    struct nodees *left;
    struct nodees *right;
    int values;
};

void gettree(nodees *nd, vector<int> v, vector<int> v0){
    if(v.size()==0||v0.size()==0) return;
    x = v[v.size()-1];
    nd->values = x;
    vector<int> left0, right0, tmp, left, right;
    tmp = v0;
    for(int i=0; i<v0.size(); i++){
        if(v0[i]==x){
            y = i;
            break;
        }
    }
    v.pop_back();
    v0.erase(v0.begin() + y, v0.end());
    left0 = v0;
    set<int> st;
    set<int>::iterator it;
    for(int i = 0; i < left0.size(); i++) st.insert(left0[i]);
    tmp.erase(tmp.begin(), tmp.begin() + y + 1);
    right0 = tmp;
    for(int i = 0; i < v.size(); i++){
        it = st.find(v[i]);
        if(it==st.end()){
            y = i;
            break;
        }
    }
    tmp = v;
    v.erase(v.begin() + y, v.end());
    left = v;
    tmp.erase(tmp.begin(), tmp.begin() + y);
    right = tmp;
    nd->left = (struct nodees *)malloc(sizeof(struct nodees));
    nd->right = (struct nodees *)malloc(sizeof(struct nodees));
    nd->left->values = -9;
    nd->right->values = -9;
    gettree(nd->left, left, left0);
    gettree(nd->right, right, right0);
}

int main(){
    int n, i, j, a, c;
    cin>>n;
    vector<int> v, v0;
    map<int, int> m, m0;
    struct nodees *nd = (struct nodees *)malloc(sizeof(struct nodees));
    for(i = 0; i < n; i++){
        cin>>a;
        v.push_back(a);
        m[a] = i;
    }
    for(i = 0; i < n; i++){
        cin>>a;
        v0.push_back(a);
        m0[a] = i;
    }
    gettree(nd, v, v0);
    vector<long long> add;
    add.push_back((long long)nd);
    struct nodees *ndd;
    vector<int> www;
    while(add.size()!=0){
        ndd = (struct nodees *)add[0];
        add.erase(add.begin());
        www.push_back(ndd->values);
        if(ndd->left->values > 0) add.push_back((long long)ndd->left);
        if(ndd->right->values > 0) add.push_back((long long)ndd->right);
    }
    for(int i = 0; i < www.size(); i++){
        cout<<www[i];
        if(i!=(www.size()-1)) cout<<" ";
    }
    return 0;
}

 GitHub - ZouJiu1/PAT: Zhejiang University PAT Question answer content Zhejiang University PAT Question answer content . Contribute to ZouJiu1/PAT development by creating an account on GitHub.https://github.com/ZouJiu1/PAT

Tree Traversals (Inorder, Preorder and Postorder) - GeeksforGeeks