题解 | #二叉树遍历#

#include <iostream>
#include <cstdio>

using namespace std;

typedef char ElementType;

struct TreeNode {
    ElementType data;
    TreeNode* leftChild;
    TreeNode* rightChild;

    TreeNode(char c) {
        this->data = c;
        this->leftChild = nullptr;
        this->rightChild = nullptr;
    }
};

void inOrder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    /*
     * 左子树、根、右子树
     */
    inOrder(root->leftChild);
    cout << root->data << " ";
    inOrder(root->rightChild);
}

/**
 * 全局变量，用于记录谦虚遍历序列的索引
 */
int pos = 0;

TreeNode* build(string preOrder) {
    char cur = preOrder[pos];
    pos++;
    if (cur == '#') {
        return nullptr;
    }
    TreeNode* root = new TreeNode(cur);
    root->leftChild = build(preOrder);
    root->rightChild = build(preOrder);
    return root;
}

/**
 * 二叉树遍历--华中科技大学
 * @return
 */
int main() {
    string preOrder;
    while (cin >> preOrder) {
        TreeNode* root = build(preOrder);
        inOrder(root);
        cout << endl;
    }

    return 0;
}