Linux安全网 - Linux操作系统_Linux 命令_Linux教程_Linux黑客

会员投稿 投稿指南 本期推荐:
搜索:
您的位置: Linux安全网 > Linux编程 > » 正文

POJ2255-Tree Recovery

来源: 未知 分享至:

转载请注明出处:優YoU http://user.qzone.qq.com/289065406/blog/1299063032

 

提示:二叉树遍历而已。。。给出前序和中序,求后序

解题思路

 

1、前序遍历的第一个字母必是

2、在中序遍历的字母串中找出 根字母,那么根字母左右两边的字符串就分别是它的左、右子树

3、利用递归复原二叉树(把子树看作新的二叉树)

4、后序遍历特征:后序遍历字母串 自右至左 依次为:

最外层(总树,设为第0层)右子树的根,内1层右子树的根,内2层右子树的根….n层右子树的根,内n层左子树的根,内n-1层左子树的根……1层左子树的根,最外层(总树,第0层)左子树的根。把总树的左子树作为新的总树,继续递归即可。   (注意:总树的叶就是作为“单叶”这棵树本身的右根)

5、输出后序遍历时,只需按4的顺序从左到右排列,再倒置输出即可

 

 1 //Memory Time 
2 //180K 0MS
3
4 #include<iostream>
5 #include<cstring>
6 using namespace std;

Tags:
分享至:
最新图文资讯
1 2 3 4 5 6
验证码:点击我更换图片 理智评论文明上网,拒绝恶意谩骂 用户名:
关于我们 - 联系我们 - 广告服务 - 友情链接 - 网站地图 - 版权声明 - 发展历史