1086. Tree Traversals Again (25)-树的遍历
2024-08-25 11:26:25
题意:用栈的push、pop操作给出一棵二叉树的中序遍历顺序,求这棵二叉树的后序遍历。
需要一个堆结构s,一个child变量(表示该节点是其父亲节点的左孩子还是右孩子),父亲节点fa
对于push v操作:
1).第一个push肯定是根节点root。
2).根据child变量,建立fa与v的父子关系。
3).由于是中序遍历,所以接下来的节点必定是v的left(如果有的话),child=left,fa=v;
4).然后进行push操作
对于pop操作:
1).根据中序遍历性质,可知接下来的节点必定是pop节点的右孩子(如果有的话),child=right,fa=s.top()
2).进行pop操作。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <cmath>
#include <stack>
#define LEFT 0
#define RIGHT 1
using namespace std; const int maxn=;
stack<int> s; struct Node{
int left=-;
int right=-;
}node[maxn]; bool first=true;
void postOrder(int u){
if(u==-)
return;
postOrder(node[u].left);
postOrder(node[u].right);
if(first){
first=false;
printf("%d",u);
}
else{
printf(" %d",u);
}
}
int main()
{
int n,v;
int root=-,fa;
int child=LEFT;
char str[];
scanf("%d",&n);
while(scanf("%s",str)!=EOF){
//if(str[0]=='y')
// break;
if(strcmp(str,"Push")==){
scanf("%d",&v);
if(root==-){
root=v;
}
else{
if(child==LEFT){
node[fa].left=v;
}
else{
node[fa].right=v;
}
}
fa=v;
child=LEFT;
s.push(v);
}
else{
child=RIGHT;
fa=s.top();
s.pop();
}
}
postOrder(root);
return ;
}
最新文章
- js(jquery)代码在页面上实时地显示时间
- SGU101
- Ffmpeg解析media容器过程/ ffmpeg 源代码简单分析 : av_read_frame()
- 安装Ubuntu双系统系列——安装Ubuntu
- Eclipse Memory Analysis进行堆转储文件分析
- 通过DAC来连接SQL Server
- Java ClassLoader基础及加载不同依赖 Jar 中的公共类(转)
- cdh4.1.2 hadoop和oozie集成问题
- hdoj 1874 畅通工程续(单源最短路+dijkstra)
- 透过浏览器看HTTP缓存(转)
- js获取屏幕和窗口的信息
- NoSql研究报告
- 局部加权回归LOWESS
- C#中使用Bogus创建模拟数据
- log4j:WARN Please initialize the log4j system properly解决办法
- WinSDK-键盘消息
- 连接PL/SQL
- Linux系统下yum源配置(Centos 6)
- java 模拟登录新浪微博(通过cookie)
- laravel 登录后跳转原来浏览的页面
热门文章
- TiDB数据库集群安装以及注意事项
- [ML学习笔记] 决策树与随机森林(Decision Tree&;Random Forest)
- FastDFS分布式文件系统设计原理
- NOI 2018网络同步赛(游记?)
- C#实现之(自动更新)
- pyspider爬取数据存入es--1.安装驱动
- tomcat-在cmd窗口启动Tomcat
- Android APK 签名比对(转)
- WPF Get jiayuan outbox list(send mail box)
- iterms 快捷键