当前位置：首页 > 编程日记 > 正文

1086 Tree Traversals Again

编程日记 2024-09-07 02:10:00

1. 这题的核心部分是，根据二叉树的先序序列和中序序列求后序序列。等于是在1020 Tree Traversals这一题的基础上，把怎么得到先序序列和中序序列的难度加大了，不是直接给出，而是要曲折一点得到。

2. 先序序列的得到就是把Push后面的数字按顺序存进pre[]数组，中序序列的获得则需要一个栈，根据入栈出栈结果存进in[]数组。

3. 至于输入的时候，一直纠结要不要用string，遇到有空格的输入怎么办，怎么把整数分割出来。其实可以不用string的，直接用字符数组，然后使用strcmp()函数判断是Push还是Pop。要是Push再读入一个整数就是了。

AC代码

#include<cstdio>
#include<map>
#include<set>
#include<string>
#include<cstring>
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>using namespace std;const int maxn = 30;int pre[maxn];
int preIdx = 0; 
int in[maxn];
int inIdx = 0;
int n;//结点总数 struct Node{int data;Node* left;Node* right;
};Node* create(int preL,int preR,int inL,int inR){if(preL>preR)return NULL;Node* root = new Node;//当前二叉树的根节点root->data = pre[preL];//当前根节点一定是先序序列的第一 int k;for(k = inR;k >= inL;k--){if(in[k]==pre[preL])break;//找到当前根结点在中序序列中的位置k }int leftNum = k - inL;//左子树的个数root->left = create(preL+1,preL+leftNum,inL,k-1);root->right = create(preL+leftNum+1,preR,k+1,inR);return root; 
}void PostOrder(Node* root){if(root == NULL)return;PostOrder(root->left);PostOrder(root->right);printf("%d",root->data);if(--n)printf(" ");
}int main(){scanf("%d",&n);char str[10];stack<int> st;int num;for(int i=0;i<2*n;i++){scanf("%s",str);if(!strcmp(str,"Push")){//说明是Push语句 scanf("%d",&num);pre[preIdx++] = num;st.push(num);}else{//说明是Pop语句 in[inIdx++] = st.top();st.pop(); }	}//根据先序和中序序列创建二叉树 Node* root = create(0,n-1,0,n-1);//进行后序输出 PostOrder(root);return 0;
}

https://www.dkcj.cn/info/17618.html

1086 Tree Traversals Again

相关文章：

Eclipse的Java工作集和多工程构建路径

ORA-08002: sequence MySeq.currval is not yet defined in this session

【Vegas原创】exp时，ORA-00932: 数据类型不一致解决方法

1102 Invert a Binary Tree 需再做

iOS安全攻防(八)Thoes的Logos简介

Algs4-1.1.13编写一段代码，打印出一个M行N列的二维数组的转置(交换行和列）

1053 Path of Equal Weight

MapXtreme 2005 学习心得在地图上创建点/线并显示标注(五)

无人驾驶——对frenet坐标的理解

1079 Total Sales of Supply Chain

在VS下用C语言连接SQLServer2008

canvas.width和canvas.style.width区别以及应用

vj p1042捕风捉影题解

1090 Highest Price in Supply Chain 需再做

有关Adobe公司的PostScript语言授权问题

INTERSECT/EXCEPT VS. IN/NOT IN

聊聊storm的stream的分流与合并

1106 Lowest Price in Supply Chain

积极拥抱.NET Core开源社区

13_文件的操作模式

Vcastr 2.2 flv 网络播放器参数设置

1094 The Largest Generation

JS魔法堂：mmDeferred源码剖析

asp vb 插入,更新,删除数据库操作。

第五次作业：四则运算之升级

妙用vector:根据第一个不等的元素比较两个序列大小的利器

四个超好用的优质资源搜索网站，海量优质资源等你发现！

sql server 2008 修改sa密码

Sql Server数据库连接Oracle数据库

普通二叉树、二叉查找树、平衡二叉树常见操作汇总