题目描述
An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.
Figure 1
输入描述:
Each input file contains one test case. For each case, the first line contains a positive integer N (<=30) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2N lines follow, each describes a stack operation in the format: "Push X" where X is the index of the node being pushed onto the stack; or "Pop" meaning to pop one node from the stack.
输出描述:
For each test case, print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space, and there must be no extra space at the end of the line.
输入例子:
6Push 1Push 2Push 3PopPopPush 4PopPopPush 5Push 6PopPop
输出例子:
3 4 2 6 5 1
解题思路：
根据题意可知， 栈的数据压入为二叉树的前序，栈的弹出为中序，求后序遍历 一般是通过前序、中序来构造二叉树，然后在遍历出后序遍历即可
版本一：
该版本的缺陷是，当出现相同数字时，无法在中序中确定谁是根节点！
1 #include2 #include 3 #include 4 5 using namespace std; 6 7 struct Node 8 { 9 int val;10 Node* l;11 Node* r;12 Node(int a = -1) :val(a), l(nullptr), r(nullptr) {}13 14 };15 16 //通过前序、中序构造二叉树17 Node* Create(const vector dataPre, const vector dataOrd,18 int preL, int preR, int ordL, int ordR)//数据源，前序的左右边界，中序的左右边界19 {20 if (preL < preR)21 return nullptr;22 Node* root = new Node();23 root->val = dataPre[preL];//根节点24 int k = ordL;25 while (dataOrd[k] != dataPre[preL])26 ++k;27 k = k - ordL;//左子树个数28 root->l = Create(dataPre, dataOrd, preL + 1, preL + k, ordL, ordL + k - 1);//构造左子树29 root->r = Create(dataPre, dataOrd, preL + k + 1, preR, ordL + k + 1, ordR);//构造右子树30 return root;31 }32 33 //后序遍历34 void LastTravle(vector &res, Node* root)35 {36 if (root == nullptr)37 return;38 LastTravle(res, root->l);39 LastTravle(res, root->r);40 res.push_back(root->val);41 }42 43 44 int main()45 {46 int N;47 cin >> N;48 N = 2 * N;49 stack data;50 vector dataPre, dataOrd;51 while (N--)52 {53 string str;54 cin >> str;55 if (str == "Push")56 {57 int a;58 cin >> a;59 dataPre.push_back(a);60 data.push(a);61 }62 else63 {64 dataOrd.push_back(data.top());65 data.pop();66 }67 }68 Node* root;69 root = Create(dataPre, dataOrd, 0, dataPre.size() - 1, 0, dataOrd.size() - 1);70 vector res;71 LastTravle(res, root);72 for (int i = 0; i < res.size() - 1; ++i)73 cout << res[i] << " ";74 cout << res[res.size() - 1] << endl;75 }
版本二：
使用key，避免了重复数字的尴尬，也不需真正构造一颗二叉树
1 #include2 #include 3 #include 4 using namespace std; 5 vector pre, in, post, value; 6 void postorder(int root, int start, int end) { 7 if (start > end) return; 8 int i = start; 9 while (i < end && in[i] != pre[root]) i++;10 postorder(root + 1, start, i - 1);11 postorder(root + 1 + i - start, i + 1, end);12 post.push_back(pre[root]);13 }14 int main() {15 int n;16 cin >> n;17 n = 2 * n;18 stack s;19 int key = 0;20 while (n--) {21 string str;22 cin >> str;23 if (str.length() == 4) {24 int num;25 cin >> num;26 value.push_back(num);27 pre.push_back(key);28 s.push(key++);29 }30 else {31 in.push_back(s.top());32 s.pop();33 }34 }35 postorder(0, 0, pre.size() - 1);36 printf("%d", value[post[0]]);37 for (int i = 1; i < n; i++)38 printf(" %d", value[post[i]]);39 return 0;40 }