题解 | #二叉树遍历#

#include <iostream>
using namespace std;

int pos;
string str;

struct Node {
    char data;
    Node * leftT;
    Node * rightT;
    Node(char c) : data(c), leftT(NULL), rightT(NULL){}
};

Node * buildTree(){
    char c = str[pos ++];
    if(c == '#')
        return NULL;

    //先序遍历（根、左、右）
    Node * node = new Node(c);
    node->leftT = buildTree();
    node->rightT = buildTree();
    return node;

}

//中序遍历
void midOrder(Node * node){
    if (node == NULL) {
        return;
    }
    midOrder(node->leftT);
    cout << node->data << ' ';
    midOrder(node->rightT);

}

int main() {
    while (cin >> str) {
        pos = 0;
        Node * root = buildTree();
        midOrder(root);
    }

    return 0;
}