PAT甲级1086 Tree Traversals Again：[C++题解]二叉树中序序列 栈 求后序遍历

文章目录

题目分析

分析： 给定栈模拟的二叉树的中序序列。

我们可以发现一些性质：

1 第一个值是根结点。

2 对于所有的push操作，如果上一个是push，该结点就是上一个结点的左儿子；如果上一个是pop，该结点就是上一个结点的右儿子。换句话说，就是一次性压入所有连通的左儿子，push1的时候，发现1有左儿子2，把2push进来，发现2有左儿子3，把3push进来，如果3有左儿子，也把3的左儿子push进来。 如果是pop操作，看该结点有没有右儿子，如果有右儿子就push进来。

代码的话，使用两个数组l[ ] 和r[ ] 存左儿子和右儿子，从根结点开始。

构建好树之后，就是后序遍历了，写一个递归函数即可。

// 后序遍历二叉树//传入 root的目的是不输出行末空格void dfs(int u ,int root) {//l[]和 r[]中空的位置if(u == 0) return;//递归左子树dfs(l[u],root);//递归右子树dfs(r[u],root);//输出根结点cout<<u;if(u!= root) cout<<" ";}

ac代码

#include<bits/stdc++.h>using namespace std;const int N = 40;int l[N] ,r[N]; //存左儿子，右儿子int n;// 后序遍历二叉树//传入 root的目的是不输出行末空格void dfs(int u ,int root) {//l[]和 r[]中空的位置if(u == 0) return;//递归左子树dfs(l[u],root);//递归右子树dfs(r[u],root);//输出根结点cout<<u;if(u!= root) cout<<" ";}int main(){cin>> n;int root; //记录根结点int last =0; //上一个点int type; //类型:push 还是popstack<int > stk;for(int i=0; i< 2* n; i++){string op;cin>>op;if(op=="Push"){int x;cin>> x;//第一个值是根结点if(last == 0) root = x; else{//上一次操作是push：type ==0if(type == 0) l[last]= x; //last的左儿子是xelse r[last] =x; // last的右儿子是x}stk.push(x);last = x;type = 0; //表示push}else{//pop操作时last = stk.top();stk.pop();type =1; //表示pop}}dfs(root,root); //后序遍历}

题目链接

PAT甲级1086 Tree Traversals Again