No BFS, começamos a atravessar a partir de 1 (o nó raiz) e visitamos seus nós filhos 8, 5 e 2. Armazená-los na ordem em que foram visitados. Isso nos permitiria visitar os nós filhos de 8 primeiro (ou seja, 6, 4 e 3), depois de 5 (ou seja, nulo) e depois de 2 (ou seja, 9) e assim por diante.
Implementação
Para implementar o BFS, um fila estrutura de dados é usada. A fila armazena o nó e o marca como ‘visitado’ até que todos os seus vértices adjacentes sejam marcados.
A fila segue o método FIFO (primeiro a entrar, primeiro a sair). Isso significa que os vizinhos do nó serão visitados na ordem em que foram inseridos.
Feitiço BFS:
- Adicionar um nó à fila
- Remover nó
- Recupere vizinhos não visitados do nó removido e adicione-os à fila
- Repita as etapas 1, 2 e 3, desde que a fila não esteja vazia.
Agora, vamos examinar alguns problemas do Leetcode e aplicar o que aprendemos.
102. Transversal de ordem de nível de árvore binária (dificuldade: média)
A pergunta nos pede para percorrer o gráfico e imprimir os nós em cada nível em uma lista vinculada. Para resolver este, tudo o que precisamos fazer é aplicar nosso feitiço!
Certifique-se de entender bem o código, pois esse é o modelo básico usaremos para resolver vários problemas. Então, vamos passar por isso.
No código acima, primeiro inserimos o nó raiz na fila. Enquanto a fila não está vazia, removemos esse nó da fila e inserimos seu filho esquerdo e direito na fila.
Mas antes disso, verificamos se cada um de seus filhos é nulo ou não. Se nulo, teríamos recebido uma exceção de ponteiro nulo.
O processo é repetido novamente com os próximos elementos que permanecem na fila. o para laço é mantido para fornecer a lista de nós em cada nível em listas vinculadas separadas.
637. Média de níveis em uma árvore binária (Dificuldade: Fácil)
Esta pergunta nos diz para encontrar o valor médio dos nós em cada nível de uma árvore binária em uma matriz. Isso segue o mesmo procedimento que o nosso problema anterior, com um pequeno ajuste.
Como você pode ver, tudo o que fizemos foi copiar e colar o código do modelo. Em seguida, simplesmente colocamos uma variável sum no loop for que pode nos dar a soma dos valores dos nós em cada nível. É isso que usaremos para calcular nossa média desejada.
429. Ordem de nível de árvore N-ária, transversal (Dificuldade: Média)
Uma árvore na qual cada nó possui não mais que N número de filhos é chamado de árvore N-ária.
Isso segue exatamente o mesmo procedimento que a travessia de uma árvore binária, exceto pelo fato de que aqui inserimos todos os filhos de um nó na fila. Lembre-se de que, ao resolver problemas relacionados à árvore binária, apenas inserimos os filhos esquerdo e direito de qualquer nó na fila.
Isso é tudo! Espero que isso tenha ajudado você a entender melhor o BFS e que tenha gostado do tutorial. Por favor, recomende este post se você acha que pode ser útil para outra pessoa!