Reconhecendo problemas de árvore

Uma árvore binária é como uma lista ligada que se ramifica: cada nó aponta para até dois filhos (esquerdo e direito). Essa ramificação é o portal para a recursão — a ferramenta que resolve a maioria dos problemas desta seção quase sozinha.

Como sempre, cada aula de padrão abre com um 🎯 Tente primeiro.

O nó: TreeNode

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left      # filho esquerdo (ou None)
        self.right = right    # filho direito (ou None)

Você guarda só a raiz (root). A partir dela, desce pelos left/right até bater em None (uma folha não tem filhos). Vocabulário rápido: raiz (topo), folha (sem filhos), altura (h, o caminho mais longo da raiz a uma folha), subárvore (qualquer nó com seus descendentes).

No editor das aulas você usa TreeNode real. Nas visualizações, representamos a árvore por três arrays (valores, esquerda, direita, com índices de filhos) para conseguir desenhá-la a cada passo — é a mesma árvore, esquerda[i] é o nó.left.

Por que recursão é a ferramenta natural

A definição de árvore é recursiva: uma árvore é um nó cujos filhos são... árvores menores. Então quase todo problema se resolve com a mesma receita:

Resolva o problema para os filhos (recursão), depois combine os resultados no nó atual. O caso-base é a árvore vazia (None).

Em vez de pensar na árvore inteira de uma vez, você confia que a recursão resolve as subárvores e só decide como juntar. Essa mudança de perspectiva é o coração da seção.

As três travessias (DFS)

Visitar todos os nós "indo fundo" (DFS) tem três ordens, que diferem em quando você processa o nó em relação aos filhos:

Veja as três numa árvore montada à mão:

Big-O em árvores: O(n) e O(h)

Duas medidas que vão aparecer o tempo todo — e que você deve sempre justificar:

• Tempo O(n): percorrer a árvore visita cada nó uma vez (n = número de nós). A maioria dos algoritmos de árvore é O(n).
• Espaço O(h): a recursão empilha uma chamada por nível em que está mergulhada; no fundo, a pilha tem o tamanho da altura h. Aqui mora a sutileza:
  • Árvore balanceada: h ≈ log n → espaço O(log n). 🎉
  • Árvore degenerada (vira uma "lista", cada nó com um filho só): h = n → espaço O(n). 😬

Por isso "O(h)" é a forma honesta de dizer o espaço da recursão: ele é ótimo quando a árvore é balanceada e ruim quando é degenerada. Guarde essa distinção — ela reaparece na BST (busca O(h)) e justifica por que árvores balanceadas importam tanto.

Os problemas da seção

• Maximum Depth, Invert Tree, Same Tree → DFS recursivo
• Level Order Traversal → BFS por níveis
• Validate BST, Kth Smallest, Lowest Common Ancestor → propriedades de BST
• Construct from Traversals, Serialize/Deserialize → construção
• Implement Trie → árvore de prefixos

Resumo

• Árvore = nós com left/right; guarda-se a raiz; folha não tem filhos.
• Recursão é natural: resolva os filhos, combine no nó, caso-base = None.
• Travessias DFS: pré, em (crescente em BST!) e pós-ordem.
• O(n) de tempo; O(h) de espaço (log n se balanceada, n se degenerada).

Próxima aula: o template recursivo que destrava a maioria das árvores.