首页 > 代码库 > POJ2255-已知二叉树前序中序求后序
POJ2255-已知二叉树前序中序求后序
水题……也可以不建立二叉树来做
如果pre[pl:pr]对应in[il:ir],那么pre[pl]是这棵树的根,它在in的位置记为root,显然root在[il,ir]内
那么二叉树的左子树是in[il:root-1],也即pre[pl+1:pl+root-il]
二叉树的右子树是in[root+1,ir],也即pre[pl+root-il+1:pr]
按照左子树-右子树-树根的后序遍历方式输出即可
附代码
#include <string> #include <iostream> #include <algorithm> #define MAX 1000007 #define MAXN 1007 using namespace std; int pre[MAXN],in[MAXN]; void getpost(int prel,int prer,int inl,int inr){ //if(prel>prer||inl>inr) return; int root=inl;//root是先序的第一个节点在中序的位置 while(in[root]!=pre[prel]) root++; if(root!=inl) getpost(prel+1,prel+root-inl,inl,root-1); if(root!=inr) getpost(prel+root-inl+1,prer,root+1,inr); printf("%c",pre[prel]); } int main(){ string a,b; while(cin>>a>>b){ int len=a.length(); for(int i=0;i<len;i++){ pre[i]=a[i]; in[i]=b[i]; } getpost(0,len-1,0,len-1); printf("\n"); } return 0; } /* DBACEGF ABCDEFG BCAD CBAD */
POJ2255-已知二叉树前序中序求后序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。