首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。