题解 | #二叉树遍历#

#include<iostream>
using namespace std;

struct TreeNode{
    char ch;
    TreeNode* left;
    TreeNode* right;
};
int i = 0;
void create(string &s,TreeNode *node)
{
    if(s[i] == '#'){
        if(node->ch == ' '){
            node->ch = s[i];
            i++;
        }
        return;
    }
    if(s[i] != '#'){
        if(node -> ch == ' '){
            node->ch = s[i];
            i++;
        }
        if(node -> left == nullptr) {
            node->left = new TreeNode;
            node->left->ch = ' ';
            node->left->left = nullptr;
            node->left->right = nullptr;
        }
        if(node -> right == nullptr) {
            node->right = new TreeNode;
            node->right->ch = ' ';
            node->right->left = nullptr;
            node->right->right = nullptr;
        }
        create(s, node->left);
        create(s, node->right);
    }
}

void infixOrder(TreeNode* node)
{
    if(node == nullptr || node -> ch == '#') return;;
    infixOrder(node->left);
    cout << node->ch << " ";
    infixOrder(node->right);
}

int main(void)
{
    string s;
    cin >> s;
    TreeNode* root = new TreeNode;
    root->ch = ' ';
    root ->left= nullptr;
    root-> right = nullptr;
    create(s, root);
    infixOrder(root);
    return 0;
}