Referência para LA 3538 (Luiza)

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;

char tmp[5];
int n1, n2;
char t1[100010], t2[100010];
int d; int pos;
char str[100010];

bool eq(int r1, int r2) {
    if (t1[r1]!=t2[r2])
        return false;

    if (t1[r1]=='$')
        return true;

    return (eq(2*r1+1,2*r2+1)&& eq(2*r1+2,2*r2+2)) ||
        (eq(2*r1+1,2*r2+2) && eq(2*r1+2,2*r2+1));
}

void buildTree(char* t, int tpos) {
    if (pos<0) return;

    t[tpos]=str[pos];
    if (str[pos]=='$') {
        pos--;
        return;
    }

    pos--;
    buildTree(t,2*tpos+2);
    buildTree(t,2*tpos+1);
}

void getTree(char* t, int& n) {
    n=0;
    while (1) {
        scanf(" %s", tmp);
        if (!strcmp(tmp, "end")) break;
        if (!strcmp(tmp, "nil")) str[n++]='$';
        else str[n++]=tmp[0];
    }

    pos=n-1;
    buildTree(t,0);
}

int main() {
    scanf("%d", &d);

    while (d--) {

        getTree(t1,n1);
        getTree(t2,n2);
        printf("%s\n", eq(0,0)? "true":"false");
    }

    return 0;
}