HGFEDCBA
EDCHBGFA
BGFHEDCA
EDCBGHFA
BEGHDFCA
BGHFEDCA
typedef struct Tnode { struct Tnode * left; struct Tnode * right; char elem; } TreeNode; //根据先序,中序遍历,返回二叉树 void * getByPreInOrder(char * preorder, char * inorder, int length) { if(length<1) return NULL; TreeNode * node=malloc(sizeof(TreeNode)); node->elem=*preorder;//根节点 int rootIndex=0; while(rootIndex<length && inorder[rootIndex]!=node->elem) rootIndex++;//查找中序遍历根节点索引 //递归恢复左右子树 node->left=getByPreInOrder(preorder+1, inorder, rootIndex); node->right=getByPreInOrder(preorder+rootIndex+1,inorder+rootIndex+1, length-rootIndex-1); return node; } //后序遍历 void postOrder(void * root) { if(root==NULL) return; TreeNode* node=(TreeNode*)root; postOrder(node->left); postOrder(node->right); printf("%c",node->elem); } void main() { char * pre="ACDEFHGB"; char * in="DECAHFBG"; void * tree=getByPreInOrder(pre,in,strlen(in)); postOrder(tree); }
这道题你会答吗?花几分钟告诉大家答案吧!
扫描二维码,关注牛客网
下载牛客APP,随时随地刷题