题解 | 二叉树遍历

/*
   个人易忘：通过前序遍历序列复原二叉树。
*/

#include <iostream>
using namespace std;

struct node {
    char val;
    node *left;
    node *right;
    node(char v):val(v),left(NULL),right(NULL){}
};

node* create_tree(string str, int &pos) {
    char c = str[pos++];
    if (c=='#') {
        return NULL;
    }
    node* root = new node(c);
    root->left = create_tree(str, pos);
    root->right = create_tree(str, pos);
    return root;
}

/*
void insert(node* &root, string s, int& i) {
    if (i>=s.length()) return;
    if (!root && s[i]!='#') {
        root = new node(s[i]);
        i++;
    }
    else if (s[i]=='#') {
        i++;
        root = NULL;
        return;
    }
    insert(root->left, s, i);
    insert(root->right, s, i);
}
*/

void inOrder (node* tree) {
    if (!tree) return;
    inOrder(tree->left);
    cout << tree->val << " ";
    inOrder(tree->right);
}

int main() {
    string s;
    while(cin >> s) {
        // int len = s.length();
        int i = 0;
        node *tree = create_tree(s, i);;
        // insert(tree, s, i);
        inOrder(tree);
        cout << endl;
    }
}
// 64 位输出请用 printf("%lld")