这个题目思路其实就是先序遍历的变形。
相当于沿着先序遍历的顺序跟着构建二叉树就行。然后中序遍历这个树。
#include<iostream>
#include<string>
using namespace std;
struct tnode{
char data;
struct tnode* left;
struct tnode* right;
};
typedef struct tnode tree;
void inorder(tree* root){
if(!root) return;
inorder(root->left);
cout << root->data <<' ';
inorder(root->right);
}
tree* build(int &i,string s){
if(s[i]=='#') {
i++;
return NULL;
}
tree* root=new tree;
root->data=s[i++];
root->left=build(i,s);
root->right=build(i,s);
return root;
}
int main(){
string s;
while(cin >> s){
int i=0;
tree* root=build(i,s);
inorder(root);
cout <<'\n';
}
return 0;
}
结果: