企业官网建设流程全解析

T1. 模拟树遍历

题目链接：SOJ D1329

二叉树的中序遍历可以借助一个堆栈来用非递归的方式实现。例如，对一棵有6 66个结点的二叉树（结点键值从1 11到6 66）进行遍历，堆栈操作为：push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop()—— 其中push为入栈，pop为出栈。则这套操作对应了一棵唯一的二叉树，如下图所示。

你的任务是输出这棵树的后序遍历序列。

时间限制：1 s
内存限制：256 MB

• 输入
  输入第一行给出一个正整数N NN（≤ 30 ≤ 30≤30），是二叉树中结点的个数（结点键值从1 11到N NN）。
  随后2 N 2N2N行，每行给出一个堆栈操作：Push X表示将键值为X的结点入栈，Pop表示将一个结点出栈。
• 输出
  在一行中输出该树后序遍历的序列。数字间以1 11个空格分隔，行首尾不得有多余空格。裁判保证输入数据一定对应了一棵树。
• 样例输入

  6 Push 1 Push 2 Push 3 Pop Pop Push 4 Pop Pop Push 5 Push 6 Pop Pop

• 样例输出

  3 4 2 6 5 1

思路分析

此题考查二叉树遍历，有一定难度。

首先要理解清楚二叉树中序遍历的栈模拟过程，栈中保存的是待处理的结点，每个Push X表示X XX是当前路径的左孩子，Pop表示当前结点无左子树 / 左子树已处理完，需处理右子树。

构建树的关键就在于记录每个结点的父节点及左右孩子：Push时，新结点为栈顶结点的左孩子；Pop后，栈顶结点的右孩子为下一个Push的结点。于是就可以得到下面的算法：

• 遇到Push X：若栈非空，X XX为栈顶结点的左孩子；将X XX入栈；
• 遇到Pop：弹出栈顶结点，记录该结点为已处理的左子树，若下一个操作是Push Y，则Y YY为该弹出结点的右孩子。

/* * Name: T1.cpp * Problem: 模拟树遍历 * Author: Teacher Gao. * Date&Time: 2026/05/09 19:04 */#include<bits/stdc++.h>usingnamespacestd;intN,L[35],R[35];voidDFS(intrt){if(!rt)return;DFS(L[rt]);DFS(R[rt]);cout<<rt<<" ";}intmain(){ios::sync_with_stdio(false),cin.tie(0);cin>>N;stack<int>st;introot=0,x,tmp,flag=0;string op;for(inti=1;i<=2*N;++i){cin>>op;if(op=="Push"){cin>>x;// 中序遍历第一个入栈的是根节点if(!root)root=x;// 如果上一次是入栈，则说明 x 是栈顶元素的左子树if(flag)L[st.top()]=x;elseR[tmp]=x;flag=1;st