Pular para o conteúdo

Espelhar uma árvore binária

Fácil#recursion#tree-traversal~10 min

A missão

Problema

Um motor de layout guarda uma página como uma árvore binária, e idiomas escritos da direita para a esquerda precisam do layout inteiro invertido. Dada a raiz de uma árvore binária, troque os filhos esquerdo e direito de todos os nós para que a árvore vire a própria imagem espelhada, e retorne a raiz. A árvore tem até 100 nós. Os exemplos mostram o resultado lido nível a nível, da esquerda para a direita.

Exemplos

Input:  tree = 4, left 2 (children 1 and 3), right 7 (children 6 and 9)
Output: [4, 7, 2, 9, 6, 3, 1]
Por quê: o 7 agora fica à esquerda, e todo nível é lido de trás para frente
Input:  tree = 2, left 1, right 3
Output: [2, 3, 1]
Input:  tree = empty
Output: []
Por quê: edge case: não há nada para inverter

Dicas

0 / 3

Tempo-alvo
O(n)
Espaço-alvo
O(h)

Restrições

  • n ≤ 100 nodes

Travou na ideia, e não no código? Árvores binárias explica isso.

Python 3Ctrl+Enter executa