Pular para o conteudo principal
SeniorPath
Explorar conteudo
Menu / Fechar menu

24 de Março

Serializar e desserializar árvore binária

Como transformar uma árvore em string e reconstruí-la preservando os nulls que definem a forma.

Árvores Avancado 30 min TypeScript

#interviews#trees#dfs#design

Implemente a serialização e a desserialização de uma árvore binaria.

Na versão original, a interface costuma vir como uma classe Codec com:

  • serialize(root): string
  • deserialize(data): TreeNode | null

Aqui no SeniorPath, use:

  • runCodec(root)

E retorne um objeto com:

  • serialized: a string produzida pela serialização
  • deserialized: a árvore reconstruida

Para manter a comparação deterministica, use:

  • pre-ordem
  • # para null
  • , como separador

Exemplo:

Input:  root = [1,2,3,null,null,4,5]
Output: serialized = "1,2,#,#,3,4,#,#,5,#,#"

A desserialização precisa reconstruir a mesma estrutura original.

O que perceber antes de codar

  • Só guardar os valores não basta. Os `null` carregam parte da estrutura.
  • Serializar e desserializar precisam concordar no mesmo protocolo.
  • O percurso em pre-ordem funciona bem porque você escreve e le a árvore no mesmo fluxo recursivo.

Erros comuns

  • omitir os `null` e perder informação estrutural
  • desserializar lendo os tokens sem manter uma posição compartilhada

Passo 1 - Entender o que precisa sobreviver

Muita gente pensa:

  • "eu salvo os valores da árvore"

Só isso não resolve.

Porque duas árvores diferentes podem ter os mesmos valores em ordens parecidas.

O que precisa sobreviver e:

  • os valores
  • a estrutura

Passo 2 - Escrever um protocolo simples

Um protocolo bom aqui e:

  • pre-ordem
  • valor normal para no real
  • # para null

Exemplo:

  • no 1
  • depois esquerda
  • depois direita

Isso gera uma sequência que já carrega a forma da árvore.

Passo 3 - Fazer a versão mais direta

A versão mais direta para desserializar e:

  • dividir a string em tokens
  • usar shift() para consumir o próximo item
  • reconstruir recursivamente

Funciona.

Mas em JavaScript, shift() em array custa O(n), porque move todo o resto.

Passo 4 - Trocar shift() por cursor

O protocolo não precisa mudar.

O que muda e só a leitura:

  • em vez de remover o primeiro token toda vez
  • mantenha um indice position
  • leia tokens[position] e avance

A ideia continua igual. Só para de pagar o custo escondido do array.

O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.

Codigo inicial

export function runCodec(root) {
  // root is an object like { val: number, left: ..., right: ... } or null
  // retorne { serialized: string, deserialized: tree }
  return { serialized: "", deserialized: null }
}
solution.ts
Travado? Dicas disponiveis.

Ainda não resolveu?

Ver a solução agora pode reduzir o aprendizado. Vale a pena tentar mais um pouco.

Abrir a solucao de referencia

Sem JavaScript, a solucao de referencia aparece inline em vez de um dialogo.

Solução

Complexidade final

Tempo: O(n)

Espaço: O(n)

Solução 1 - Pre-ordem com shift() na volta

Boa versão inicial porque deixa o protocolo muito visível.

function serialize(root) {
  if (root === null) {
    return "#"
  }

  return `${root.val},${serialize(root.left)},${serialize(root.right)}`
}

function deserialize(data) {
  const tokens = data.split(",")

  function build() {
    const token = tokens.shift()

    if (token === "#" || token === undefined) {
      return null
    }

    return {
      val: Number(token),
      left: build(),
      right: build(),
    }
  }

  return build()
}

export function runCodec(root) {
  const serialized = serialize(root)

  return {
    serialized,
    deserialized: deserialize(serialized),
  }
}

Funciona.

Mas o shift() deixa a desserialização mais cara do que parece.

Solução 2 - Pre-ordem com cursor usando busca em profundidade (DFS) em O(n)

Agora o protocolo continua o mesmo, mas a leitura fica linear de verdade.

function serialize(root) {
  if (root === null) {
    return "#"
  }

  return `${root.val},${serialize(root.left)},${serialize(root.right)}`
}

function deserialize(data) {
  const tokens = data.split(",")
  let position = 0

  function build() {
    const token = tokens[position]
    position += 1

    if (token === "#") {
      return null
    }

    return {
      val: Number(token),
      left: build(),
      right: build(),
    }
  }

  return build()
}

export function runCodec(root) {
  const serialized = serialize(root)

  return {
    serialized,
    deserialized: deserialize(serialized),
  }
}

O insight forte aqui e que serialização e desserialização sao duas metades do mesmo contrato.

O que dizer na entrevista

Uma explicação curta e boa seria:

Eu uso pre-ordem com marcador de null, porque isso preserva tanto os valores quanto a estrutura. Na volta, leio os tokens na mesma ordem recursiva. A versão forte evita shift() e usa um cursor compartilhado para consumir a string em O(n).

Isso mostra que você:

  • pensou em protocolo, não só em travessia
  • protegeu a estrutura da árvore
  • enxergou um custo escondido da implementação

Quando esse padrão aparece de novo

Esse padrão reaparece quando você precisa:

  • transformar estrutura em representação transportavel
  • reconstruir estado a partir de um protocolo
  • decidir que informação estrutural precisa ser explicita
  • usar busca em profundidade (DFS) como forma de escrita e leitura

O ponto não e decorar esse problema.

O ponto e aprender que serializar bem começa definindo o contrato certo.
Proximo desafio Mediana em fluxo de dados Desafio anterior Matriz espiral

Desafios relacionados

Inverter árvore binária

Travessia em níveis da árvore binária

Profundidade máxima de árvore binária

Artigos relacionados

Enquadrar o problema antes de codificar

Como Explicar sua Solução sem se Perder

Reconhecer padrões em problemas