Recentemente, comecei a praticar alguns exercícios de LeetCode para melhorar minhas habilidades de algoritmo/estrutura de dados. Posso dizer que a plataforma oferece um bom ambiente para praticar e aprender com outros desenvolvedores soluções em diversas linguagens de programação, discutir, compartilhar soluções com outras pessoas e praticar desafios de código solicitados por grandes empresas.

O que é LeetCode?

LeetCode é um site que ajuda os candidatos a se prepararem para entrevistas de codificação. Os usuários podem praticar desafios usando a codificação e problemas algorítmicos da plataforma, juntamente com testes predefinidos para a solução do candidato. LeetCode se tornou um recurso popular para entrevistas técnicas e competições de codificação, junto com o HackerRank.

Minha rotina resolvendo problemas

Eu me propus a resolver pelo menos 3 desafios por dia, e minha forma de pensar em uma solução envolve meu iPad, uma caneta para telas e o aplicativo Freeform. Procuro desenhar e pensar nas soluções, e isso está ajudando muito nos meus envios de código. Muitos desafios parecem difíceis à primeira vista, mas com alguns minutos pensando e arquitetando a solução (recomendo escrever seu processo de pensamento). Se não consigo encontrar a solução certa em 30 minutos, então vejo o envio de outros desenvolvedores para descobrir onde estão meus erros (às vezes um pequeno passo que esqueci no meu código). Mesmo que sua solução seja boa o suficiente, recomendo fortemente que você analise os envios de outras pessoas para pensar em outras maneiras de resolver esse problema (algumas mais ou menos eficientes).

O problema da árvore binária invertida

Há poucos dias enfrentei o problema de Inverter Árvore Binária no LeetCode, um conhecido desafio solicitado em algumas entrevistas e um problema que percebi ao fazer aulas de Estruturas de Dados/Algoritmos na universidade. Embora eu nunca tenha enfrentado esse desafio em uma entrevista e nunca tenha tido que inverter explicitamente uma árvore binária em meu trabalho, saber como inverter uma me deu mais experiência com DS, árvores e pensamento de algoritmo e pratique algumas técnicas como recursão. ]
Recomendo que você tente resolver esse problema antes de ler o restante deste artigo

A solução

O problema de Inverter Árvore Binária me pediu para "Dada a raiz de uma árvore binária, inverter a árvore e retornar sua raiz." (em outras palavras, deveríamos “espelhar” a árvore). Usei a linguagem de programação Java para enviar uma solução, mas os passos são os mesmos para outras linguagens (com pequenas alterações de sintaxe). O exemplo de entrada e a saída esperada são mostrados abaixo:

Entrada: raiz = [4,2,7,1,3,6,9] Saída: [4,7,2,9,6,3,1]

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Vamos usar a técnica de recursão para chamar recursivamente o método invertTree(), passando algum lado da árvore como raiz. Então, como toda recursão pede, precisamos definir uma condição de parada onde a pilha de recursão terminará e retornará o respectivo resultado da chamada de recursão. Depois, apenas invertemos os lados da árvore, atribuindo a root.left o valor retornado pela recursão passando root.right como parâmetro, e fazemos o mesmo para root.right atribuindo o valor do resultado da recursão root.left.

Como estamos modificando o valor original, precisamos de uma variável auxiliar para armazenar o resultado original de root.left (você provavelmente implementou um código como este na universidade e o chamou de método swap().

No final retornamos a raiz com os nós invertidos. Você pode verificar o código abaixo:

/** * Definição para um nó de árvore binária. * classe pública TreeNode { * valor interno; * TreeNode à esquerda; * TreeNode à direita; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode à esquerda, TreeNode à direita) { * este.val = val; * this.left = esquerda; * this.right = certo; * } * } */ classe Solução { public TreeNode invertTree(raiz TreeNode) { if(raiz == nulo) { retornar nulo; } TreeNode aux = root.left; root.left = invertTree(root.right); root.right=invertTree(aux); retornar raiz; } }

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Tenha em mente que podem existir muitas soluções diferentes para problemas diferentes, e isso é ótimo. Todo mundo tem uma maneira de pensar e programar, domínio de Estruturas de Dados etc. Você não precisa seguir exatamente esse mesmo código para resolver esse problema, mas deve prestar atenção na complexidade do algoritmo (você pode usar 3 aninhados para resolver um problema , mas isso é menos performático do que usar 1 for).