题解 | #二叉树遍历#

#include<iostream>
#include<string>
using namespace std;

struct node{//结点
  char data;
  node* leftchild;
  node* rightchild;
  node(char c):data(c),leftchild(nullptr),rightchild(nullptr){}
};


node* build(string s1,string s2){//根据先序+中序，构造二叉树
  if(s1.size()==0)return nullptr;
  char c=s1[0];
  node* root=new node(c);
  int pos=s2.find(c);//找到分界点，pos也是左子树的长度
  
  root->leftchild=build(s1.substr(1,pos),s2.substr(0,pos));
  root->rightchild=build(s1.substr(pos+1),s2.substr(pos+1));
  return root;
}

void LRN(node* root){//后序访问
  if(root==nullptr)return;
  LRN(root->leftchild);
  LRN(root->rightchild);
  printf("%c",root->data);
}

int main(){
  string s1,s2;
  while(cin>>s1>>s2){
    node* root=build(s1,s2);
    LRN(root);
    printf("\n");

  }
  
  return 0;
}