九度 1184：二叉树遍历

#include <iostream>
#include <stdio.h>
#include <deque>
#include <set>
#include <cstring>
using namespace std;

class Node {
public:
    char data;
    Node *left, *right;

    Node(char _data):data(_data) {
        left = right = NULL;
    }
};

char seq[200];
int n;

Node* buildTree() {
    if(n == 1) {
        if(seq[0] == ‘#‘)
            return NULL;
        return new Node(seq[0]);
    }

    set<Node*> lchild;
    deque<Node*> stack;
    Node *root = new Node(seq[0]);
    stack.push_back(root);

    for(int i = 1; i < n; i ++) {
        if(seq[i] == ‘#‘) {
            Node *lastone = stack.back();
            if(lchild.count(lastone)) {
                lastone->right = NULL;
                stack.pop_back();
            }else{
                lchild.insert(lastone);
                lastone->left = NULL;
            }
        }else{
            Node *lastone = stack.back();
            Node *newNode = new Node(seq[i]);
            if(lchild.count(lastone)) {
                lastone->right = newNode;
                stack.pop_back();
                stack.push_back(newNode);// WA
            }else{
                lchild.insert(lastone);
                lastone->left = newNode;
                stack.push_back(newNode);
            }
        }
    }
    return root;
}

void inOrder(Node *root) {
    if(root == NULL)
        return;
    inOrder(root->left);
    printf("%c ", root->data);
    inOrder(root->right);
}

int main() {
    while(scanf("%s", seq) != EOF) {
        n = strlen(seq);
        Node *root = buildTree();
        inOrder(root);
        printf("\n");
    }
    return 0;
}