题解 | 二叉树遍历

#include <iostream>
#include <string>
#include <queue>
#include <stack>
using namespace std;
struct treenode{
    char data;
    treenode *left;
    treenode *right;
};
struct queuenode{
    treenode *parent;
    bool isleft;
};
void buildtree(treenode *&proot,stack<queuenode *> &a,char c){
    if (c!='#'){
        treenode *pnew=new treenode;
        pnew->data=c;
        pnew->left=nullptr;
        pnew->right= nullptr;
        queuenode *p=new queuenode;
        p->parent=pnew;
        p->isleft= false;
        if (proot== nullptr) proot=pnew;
        else{
            queuenode *pcur=a.top();
            if (pcur->isleft== false){
                pcur->parent->left=pnew;
                pcur->isleft= true;
        } else{
                pcur->parent->right=pnew;
                a.pop();
                delete pcur;
            }
    }a.push(p);
    } else {queuenode *pcur=a.top();
        if (pcur->isleft== false){
            pcur->parent->left= nullptr;
            pcur->isleft= true;
        } else{
            pcur->parent->right= nullptr;
            a.pop();
            delete pcur;
        }}
}
void midorder(treenode *proot){
    if (proot== nullptr) return;
    midorder(proot->left);
    cout<<proot->data<<' ';
    midorder(proot->right);
}
int main() {
    string s;
    cin>>s;
    treenode *proot= nullptr;
    stack<queuenode *> a;
    int i = 0;
    for (; i < s.size(); ++i) {
        buildtree(proot,a,s[i]);
        if(i==s.size()-1) break;
    }
    midorder(proot);
    return 0;
}