Portanto, antes de ler alguns conceitos básicos de ciência da computação.

1. Uma árvore binária é uma estrutura alocada dinamicamente (geralmente usada para armazenamento ordenado).
2. Por causa de sua natureza, a travessia de árvores binárias geralmente é recursiva;
   Isso ocorre porque o deslocamento linear (via loop) não é natural quando existem duas vias de loop.
   • Recursiva: significa uma função que se chama.
3. Em idiomas antiquados, o gerenciamento de memória requer gerenciamento manual de memória.
   • Manual: significa que você deve fazer isso sozinho.
4. Ao fazer o gerenciamento manual da memória, você precisa solicitar ao sistema subjacente para liberar cada membro da árvore.
   • Livre: recupere a memória para os poos globais, para que possa ser reutilizada e você não fique sem memória.
   • Liberando: isso é feito chamando a função free()e passando o ponteiro que você deseja recuperar.
   • Ponteiro: É como um bastão virtual. No final está a memória. Quando você pede memória, você recebe um ponteiro (stick virtual) que possui memória. Ao terminar, você devolve o ponteiro (bastão virtual).

A solução recursiva:

freeTree(Node* node)
{
    freeTree(node->left);  
    freeTree(node->right);
    free(node);
}

O problema é que recursão significa que você está repetidamente chamando a mesma função. Isso aumenta a pilha. Aumentar a pilha usa mais memória. A razão pela qual você está liberando a árvore é que você deseja recuperar a memória usando mais memória é contraproducente (mesmo que você recupere os dois bits de memória).

Por fim, a pergunta:

Portanto, o problema gira em torno da conversão da versão recursiva acima em uma solução linear (para que você não precise usar memória).

Dê ao tipo de nó

typedef struct Node Node;
struct Node
{
    Node* left;
    Node* right;
};

Escreva uma função para liberar uma árvore desses nós.

Restrições:

• Não é possível usar recursão (nem indiretamente)

• Não é possível alocar nenhum espaço dinâmico para rastreamento.

• Observe que existe uma solução O (n)

Vencedora:

1. Melhor complexidade.
2. Tie Break 1: Primeiro enviado
3. Tie Break 2: Menor quantidade de caracteres.

Parece muito próximo de O (n) para mim:

Isso faz uma caminhada profunda na árvore e usa o ->leftponteiro dos nós percorridos para acompanhar o pai.

struct Node * node = root;
struct Node * up = NULL;

while (node != NULL) {
    if (node->left != NULL) {
        struct Node * left = node->left;
        node->left = up;
        up = node;
        node = left;
    } else if (node->right != NULL) {
        struct Node * right = node->right;
        node->left = up;
        node->right = NULL;
        up = node;
        node = right;
    } else {
        if (up == NULL) {
            free(node);
            node = NULL;
        }
        while (up != NULL) {
            free(node);
            if (up->right != NULL) {
                node = up->right;
                up->right = NULL;
                break;
            } else {
                node = up;
                up = up->left;
            }
        }
    }
}

C99, 94, O (n)

Edit: todo mundo parece se referir struct Nodeapenas Nodecomo se o typedefed, assim como eu fiz.

este é realmente o meu primeiro golfe C. muitas segfaults.

de qualquer forma, isso requer C99 porque ele usa uma declaração dentro da primeira instrução de um loop for.

void f(Node*n){for(Node*q;n;n=q)(q=n->left)?n->left=q->right,q->right=n:(q=n->right,free(n));}

nem usando #define!

esse algoritmo funciona transformando a árvore para que o nó superior não tenha filho esquerdo e, em seguida, excluindo-o e passando para o filho certo.

por exemplo, se começarmos com a árvore

 1
/ \
2 3
 \
 4

o algoritmo mudará os ponteiros para que a árvore seja

2
 \
 1
/ \
4 3

agora podemos excluir o nó superior facilmente.

Caracteres C / C ++ / Objective-C 126 (inclui nova linha à direita necessária)

#define b(t)(t->left||t->right)
void f(Node*r){while(r&&b(r)){Node**p=&r,*c=b(r);while(c)p=&c,c=b(c);free(*p);*p=0;}free(r);}

Não é executado no tempo O (n). Mas o OP não exige, então aqui está minha solução O (n ² ).

Algoritmo: Desça até uma folha da raiz. Solte-o. Repita até que não haja folhas. Solte a raiz.

Ungolfed:

void freeTree (Node * root) {
    while (root && (root->left || root->right)) {
        Node ** prev = &root;
        Node * curr = root->left || root->right;
        while (curr != 0) {
            prev = &curr;
            curr = curr->left || curr->right;
        }
        free(*prev);
        *prev = 0;
    }
    free(root);
}

c ++ 99 O (n)

Os loops aqui são ótimos para encadear ao longo de uma lista, mas não para subir e descer hierarquias. user300 conseguiu (estou impressionado), mas o código é difícil de ler.

A solução é converter a árvore em uma lista.
O truque é fazer isso ao mesmo tempo em que você exclui os nós.

void freeNode(Node* t)
{
    if (t == NULL)
    {   return;
    }

    // Points at the bottom left node.
    // Any right nodes are added to the bottom left as we go down
    // this progressively flattens the tree into a list as we go.    
    Node* bottomLeft    = findBottomLeft(t);


    while(t != NULL)
    {
        // Technically we don't need the if (it works fine without)
        // But it makes the code easier to reason about with it here.
        if (t->right != NULL)
        {
            bottomLeft->left = t->right;
            bottomLeft = findBottomLeft(bottomLeft);
        }
        // Now just free the curent node
        Node*   old = t;
        t = t->left;
        free(old);
    }
}

Node* findBottomLeft(Node* t)
{
    while(t->left != NULL)
    {
        t = t->left;
    }
    return t;
}

Versão Golf

void f(Node*t){Node*o,*l=t;for(;t;free(o)){for(;l->left;l=l->left);l->left=t->right;o=t;t=t->left;}}

Golf Expanded

void f(Node* t)
{
        Node*o,*l    = t;

        for(;t;free(o))
        {
            for(;l->left;l = l->left);
            l->left = t->right;
            o = t;
            t = t->left;
        }
}

C, 150 bytes

f(T*r,int s){T*t[s];t[0]=r;T**f=&t[0],**e=&t[0];while(f<=e){if(*f){if((*f)->left){*++e=(*f)->left;}if((*f)->right){*++e=(*f)->right;}}free(*f);f++;}}

Experimente no JDoodle