题解 | #二叉树遍历#

//第一感觉只有前序没法确定序列，但是问题在于他把空用#表示出来了，当遇到#时，表示之后的一定不是孩子的
#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    char data;
    TreeNode* leftChild;
    TreeNode* rightChild;
};

TreeNode* Build(int& i, string str) {
    char c = str[i++];
    if (c == '#') return NULL;
    //为字符构建结点
    TreeNode* pNewNode = new TreeNode;
    pNewNode->data = c;
    pNewNode->leftChild = Build(i, str);
    pNewNode->rightChild = Build(i, str);
    return pNewNode;
}

void InOrder(TreeNode* root) {
    if (root == NULL) return;
    InOrder(root->leftChild);
    printf("%c ", root->data);
    InOrder(root->rightChild);
}

int main() {
    string str;
    while (cin >> str) {
        int i = 0;
        TreeNode* root = Build(i, str);
        InOrder(root);
        cout << endl;
    }
    return 0;
}