题解 | 二叉树遍历

#include <bits/stdc++.h>
using namespace std;

struct TNode{
    char data;
    struct TNode* left;
    struct TNode* right;
    TNode(char c):data(c),left(nullptr),right(nullptr){}
};

TNode* build(int& pos,string s){
    char c=s[pos++];
    if(c=='#')return nullptr;
    TNode* r=new TNode(c);
    r->left=build(pos,s);
    r->right=build(pos,s);
    return r;
}

void inOrder(TNode* r){
    if(r==nullptr)return;
    inOrder(r->left);
    cout<<r->data<<" ";
    inOrder(r->right);
}

int main(){
    string s;
    while(cin>>s){
        int pos=0;
        inOrder(build(pos,s));
    }
}

中序遍历并不难，核心是构建，提供的先序的字符串，所以用先序的方式对每个字符进行检索，递归逻辑是，当前所指字符即本身，如果为#则直接结束，如果为其他的，那么根据先序下一个就左子，下一轮就是右子，然后就可以写出来上述代码