洛谷题号:P1827
做过二百遍的二叉树重构了,老套路:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 | #include<iostream> #include<cstdio> #include<string> #include<algorithm> #include<queue> #include<list> #include<cstring> #include<cassert> using namespace std; char in[30],pre[30]; #define NULL 0 struct node{ char value; node * left; node * right; node(){ value = '\0'; left = NULL; right = NULL; } }; int find_in(int in_s, int in_e, char node){ for (int i = in_s; i <= in_e; i++){ if (in[i] == node)return i; } assert(0); return -1; } void BuildTree(int in_s, int in_e, int pre_s, int pre_e, node * root){ if (in_s == in_e&&pre_s == pre_e){ root->value = pre[pre_s]; return; } if (in_s > in_e || pre_s > pre_e){ return; } root->value = pre[pre_s]; int pos_in = find_in(in_s, in_e, pre[pre_s]); root->left = new node; BuildTree(in_s, pos_in - 1, pre_s + 1, pre_s + pos_in - in_s, root->left); root->right = new node; BuildTree(pos_in + 1, in_e, pre_s + pos_in - in_s + 1, pre_e, root->right); } void postorder_traversal(node * ptr){ if (ptr->left != NULL)postorder_traversal(ptr->left); if (ptr->right != NULL)postorder_traversal(ptr->right); if (ptr->value != '\0')cout << ptr->value; } int main(){ ios::sync_with_stdio(false); cin >> in+1 >> pre+1; int len = 1; while (in[len])len++; len--; node * root = new node; BuildTree(1, len, 1, len, root); postorder_traversal(root); cout << endl; } |