首页 > 代码库 > 前序遍历与中序遍历确定后序遍历
前序遍历与中序遍历确定后序遍历
1003. 二叉树后序遍历
|
||||||
|
||||||
Time Limit: 3sec Memory Limit:256MB
Description
给定一棵二叉树的前序和中序遍历顺序,输出后序遍历顺序
Input
第一行是二叉树的前序遍历顺序。二叉树的结点个数<=26,每个结点以一个大写字母表示,结点字母之间没有间隔。第二行是这棵二叉树的中序遍历顺序,表示方法和前序相同。(注:在左子树和右子树之间总是先左后右) Output
输出二叉树后序遍历的顺序 Sample Input
Copy sample input to clipboard
GDAFEMHZ ADEFGHMZ Sample Output
AEFDHZMG |
通过前序遍历与中序遍历可以唯一确定二叉树
我们先重建一棵二叉树
再后序遍历
#include <iostream> #include <string> using namespace std; //结点类 struct Node { Node * lchild; Node * rchild; char c; }; //重建后续排序二叉树 Node * rebuild(string s1, string s2) { //建立根结点 Node * t=NULL; //一定要初始化为NULL,不然报错 if(s1.size()>0){ t=new Node; t->c=s1[0]; t->lchild=NULL; t->rchild=NULL; } if(s1.size()>1){ //寻找根结点在中序遍历中的位置 int root; for(int i=0; i<s2.size(); i++){ if(s2[i]==t->c){ root=i; break; } } //左子树重建 string qianxu_left=s1.substr(1, root); //注意substr的用法,第二个参数是子字符串长度 string zhongxu_left=s2.substr(0, root); t->lchild=rebuild(qianxu_left, zhongxu_left); //右子树重建 string qianxu_right=s1.substr(root+1, s1.size()-root-1); string zhongxu_right=s2.substr(root+1, s2.size()-root-1); t->rchild=rebuild(qianxu_right, zhongxu_right); } return t; } //后序遍历:左右根 void houxu(Node * t) { //左子树非空,遍历左子树 if(t->lchild!=NULL) houxu(t->lchild); //右子树非空,遍历右子树 if(t->rchild!=NULL) houxu(t->rchild); //取出该结点的值 cout<<t->c; } int main() { string s1, s2; cin>>s1>>s2; Node * t=rebuild(s1, s2); houxu(t); cout<<endl; return 0; }
前序遍历与中序遍历确定后序遍历
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。