2012年12月18日

UVa 536 - Tree Recovery


#include <cstdio>
#include <string>
using std::string;

int now;
char pre[50], in[50];

struct Node {
  Node (char c, Node* l, Node* r) : c(c), l(l), r(r) {
  }
  char c;
  Node* l;
  Node* r;
};

Node* build(string s) {
  char c = pre[now];
  if (s.find(c) != string::npos) {
    now++;
    return new Node(c, build(s.substr(0, s.find(c))), build(s.substr(s.find(c) + 1)));
  }
  return NULL;
}

void post(Node* node) {
  if (!node) return;
  post(node->l);
  post(node->r);
  putchar(node->c);
}

int main() {
  while (scanf("%s%s", pre, in) == 2) {
    now = 0;
    post(build(string(in)));
    puts("");
  }
  return 0;
}

沒有留言:

張貼留言