binary tree is_subtree

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
// clang-format off
#define struct(x) typedef struct x x; struct x
// clang-format on
struct(node) {
    char c;
    node *l, *r;
};
#define Z NULL

node *C(char c, node *l, node *r) {
    node *n = calloc(1, sizeof(node));
    *n = (node){ c, l, r };
    return n;
}

void D(node *n) {
    if (n) D(n->l), D(n->r), free(n);
}

// a == b ?
int g(node *a, node *b) {
    if (a == Z && b == Z) return 1;
    if (a == Z || b == Z) return 0;
    return a->c == b->c && g(a->l, b->l) && g(a->r, b->r);
}

// a 包含 b ?
int f(node *a, node *b) {
    return g(a, b) || (a && (f(a->l, b) || f(a->r, b)));
}

// 简单递归解析
node *S_(const char *s, int *i) {
    #define peek s[*i]
    #define step (*i += 1)
    #define match(c) (peek == c)

    char c = peek;

    step; // skip "A", maybe ',' '(' ')'
    if (match(',') || match(')')) return C(c, Z, Z);

    step; // skip "(", maybe ',' 'B'
    node *l = match(',') ? Z : S_(s, i);

    step; // skip ",", maybe ')', 'C'
    node *r = match(')') ? Z : S_(s, i);

    step; // skip ")"
    return C(c, l, r);

    #undef match
    #undef step
    #undef peek
}

// "A(B,C)" -> C('A', C('B', Z, Z), C('C', Z, Z))
node *S(const char *s) {
    int i = 0;
    return S_(s, &i);
}

int main(void) {
    node *a = S("A(B(D,E),C(F,G(,I)))");
    node *b = S("C(F,G(,I)))");
    printf("%d\n", f(a, b));
    D(b), D(a);
    return 0;
}