题解 | #二叉树遍历#

#include <iostream>
using namespace std;
struct node {
    char c;
    node* leftChild;
    node* rightChild;
    node(char ch) {
        c = ch;
        leftChild = NULL;
        rightChild = NULL;
    }
};
int pos=0;
node* build(string preOrderStr) {
    char temp = preOrderStr[pos++];
    // preOrderStr = preOrderStr.substr(1);
    if (temp == '#') return NULL;
    node* root = new node(temp);
    root->leftChild = build(preOrderStr);
    root->rightChild = build(preOrderStr);
    return root;
}
void inOrder(node* root) {
    if (root == NULL) return;
    inOrder(root->leftChild);
    cout << root->c << ' ';
    inOrder(root->rightChild);
}
int main() {
    string preOrderStr;
    while (cin >> preOrderStr) { // 注意 while 处理多个 case
        node* tree = build(preOrderStr);
        inOrder(tree);
        cout << endl;
    }
}
// 64 位输出请用 printf("%lld")