题解 | #二叉树遍历#

难点在于递归建树

#include <ios>
#include <iostream>
using namespace std;
struct treeNode {
    char c;
    treeNode* leftChild;
    treeNode* rightChild;
    treeNode(char ch) {
        c = ch;
        leftChild=NULL;
        rightChild=NULL;
    }
};
string nodeStr;
int pos;
treeNode* buildTree() {
    char c=nodeStr[pos++];
    if (c == '#') {
        return NULL;
    }
    treeNode* newNode = new treeNode(c);
    newNode->leftChild = buildTree();
    newNode->rightChild = buildTree();
    
    return newNode;
}
void inOrder(treeNode* root) {
    if (root == NULL) return;
    inOrder(root->leftChild);
    cout << root->c << ' ';
    inOrder(root->rightChild);
}
int main() {

    while (cin >> nodeStr) { // 注意 while 处理多个 case
        pos=0;
        treeNode* root = buildTree();
        inOrder(root);
        cout  << endl;
    }
}
// 64 位输出请用 printf("%lld")