首页 > 代码库 > PAT 1086 Tree Traversals Again

PAT 1086 Tree Traversals Again

室友在做于是也做一发,跟已知两种遍历序列还原二叉树的思路类似,感觉PAT上的题目跟书本知识靠的近一些

#include <iostream>#include <cstdio>#include <vector>using namespace std;void print_data(const vector<char> &as, const vector<int> &ns) {    int len = ns.size();    for (int i=0; i<len; i++) {        if (as[i] == i) {            cout<<"push "<<ns[i]<<endl;        } else {            cout<<"pop"<<endl;        }    }}void build_postorder(vector<char> &actions, vector<int> &nums, int start, int end, vector<int> &postorder) {    if (start >= end) return;    if (actions[start] != i) return;    // root node    postorder.push_back(nums[start]);        // now try to find the seperator idx of     // action(must be a pop pair wise with root node push) between two sub tree    int pushs = 1;    int idx = start + 1;    while (pushs != 0 && idx < end) {        if (actions[idx] == i) {            pushs++;        } else {            pushs--;        }        idx++;    }        // right sub tree    build_postorder(actions, nums, idx, end, postorder);        // left sub tree    build_postorder(actions, nums, start + 1, idx, postorder);}int main() {        int N, len;        scanf("%d", &N);    len = N * 2;        char buf[10];    int num;        vector<char> actions(2 * N, \0);    vector<int> nums(2 * N, 0);        // read in data    for (int i=0; i<len; i++) {        scanf("%s", buf);            if (buf[3] == h) {            scanf("%d", &num);            nums[i] = num;            actions[i] = i;    // push, input        } else {            actions[i] = o;    // pop, output        }    }            vector<int> postorder;        build_postorder(actions, nums, 0, len, postorder);    if (postorder.size() > 0){        // print_data(actions, nums);        for (int i=N - 1; i>=1; i--) {            printf("%d ", postorder[i]);        }        printf("%d", postorder[0]);    }    return 0;}

 

PAT 1086 Tree Traversals Again