PAT 甲级 1086 Tree Traversals Again
https://pintia.cn/problem-sets/994805342720868352/problems/994805380754817024 ? 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 Input Specification:Each input file contains one test case. For each case,the first line contains a positive integer?N?(≤) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to?N). Then?2?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. Output Specification: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. Sample Input:6 Push 1 Push 2 Push 3 Pop Pop Push 4 Pop Pop Push 5 Push 6 Pop Pop Sample Output:3 4 2 6 5 1 代码: #include <bits/stdc++.h> using namespace std; int N; vector<int> in,post,pre,val; void postorder(int root,int st,int en) { if(st > en) return; int i = st; while(i < en && in[i] != pre[root]) i ++; postorder(root + 1,st,i - 1); postorder(root + 1 + i - st,i + 1,en); post.push_back(pre[root]); } int main() { scanf("%d",&N); stack<int> s; string op; int cnt = 0; for(int t = 0; t < N * 2; t ++) { cin >> op; if(op == "Push") { int x; scanf("%d",&x); pre.push_back(cnt); val.push_back(x); s.push(cnt ++); } else { in.push_back(s.top()); s.pop(); } } postorder(0,N - 1); for(int i = 0; i < N; i ++) { printf("%d",val[post[i]]); printf("%s",i != N - 1 ? " " : ""); } return 0; } push 的顺序是前序遍历的顺序 按照题目 pop 得到的中序遍历的顺便 in 和 pre 存的是数字的位置 val 求数字的值 递归求出后序遍历? FH (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
- NIKKEI Programming Contest 2019 翻车记
- Go语言实战读书笔记
- 解决Loading class `com.mysql.jdbc.Driver'. This is
- delphi的常用条件编译指令---{$IFDEF} {$UNDEF}{$IFDEF}{$E
- 数据处理中判断空值的方法(np.isnan、is np.nan和pd.isna)比
- Java Config等效于conversionService/FormattingConversion
- VB.NET之旅(十四)—动态关联事件与处理程序
- 在Perl中安装GD.pm时启用PNG支持
- 请Groovy / Grails代码清理建议!
- 斯图飞腾Stratifyd荣登2020大数据产业创新服务产品榜单