给定二叉树的先序遍历序列和中序遍历序列，进行二叉树的重建以及后序遍历队列。
突然看到这个问题。。发现之前的想法都忘记了=_=||，果然算法题一日不写手生啊，还是得好好坚持练习才行啊。
代码：
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
struct node{
char ch;
node *left;
node *right;
};
char pre[100];
char in[100];
node *rec(int s1, int e1, int s2, int e2){
node *tree = new node;
char ch = pre[s1];
tree->ch = ch;
tree->left = NULL;
tree->right = NULL;
int rootidx; //找到每一颗子树的根节点 划分左右子树
for(int i=s2; i<=e2; i++){
if(in[i] == ch){
rootidx = i;
break;
}
}
if(rootidx != s2) // 有左子树的话 那么这个字符在中序序列中肯定不是最左边的
tree->left = rec(s1+1, s1+(rootidx-s2), s2, rootidx-1);
if(rootidx != e2)
tree->right = rec(s1+(rootidx-s2)+1, e1, rootidx+1, e2);
return tree;
}
void postOrder(node *t){
if(t){
if(t->left)
postOrder(t->left);
if(t->right)
postOrder(t->right);
printf("%c", t->ch);
}
}
int main(){
while(~scanf("%s", pre)){
scanf("%s", in);
int l = strlen(pre);
node *tree;
tree = rec(0, l-1, 0, l-1);
postOrder(tree);
printf("\n");
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/116702.html
