Traversal de pré-ordem de árvore binária Kotlin (uma solução recursiva e sem usar recursão)

Este post é sobre a travessia de pré-ordem de uma árvore binária, um método de travessia da árvore na qual o nó atual é visitado antes de seus filhos. O algoritmo de travessia de pré-ordem visita primeiro o nó raiz e, em seguida, visita recursivamente a subárvore esquerda, seguida pela subárvore direita. O resultado de uma travessia de pré-ordem é uma lista dos valores dos nós na ordem em que são visitados. Este post ajudará você a entender como percorrer uma árvore binária e também como implementá-la de diferentes maneiras.

Traversal de pré-ordem é um método de percorrer uma árvore binária onde o nó atual é visitado antes de seus filhos. O algoritmo visita o nó raiz primeiro, então visita recursivamente a subárvore esquerda, seguida pela subárvore direita. O resultado de uma travessia de pré-ordem é uma lista dos valores dos nós na ordem em que são visitados.

Neste problema, você recebe a raiz de uma árvore binária representada pela classe TreeNode em Kotlin, que tem uma propriedade val para o valor do nó e propriedades left e right para seus filhos left e right, respectivamente. Sua tarefa é escrever duas implementações de uma função que executa uma travessia de pré-ordem da árvore binária e retorna uma lista dos valores dos nós. Uma deve ser uma solução recursiva e a outra não deve usar recursão.

Aqui está a assinatura de classe da função:

 fun preorderTraversal(root: TreeNode?): List<Int>

A entrada para a função é o nó raiz da árvore binária e a saída é uma lista de inteiros representando os valores dos nós na ordem em que são visitados durante a travessia de pré-ordem.

Descrições:

Dada a raiz de uma árvore binária, retorne a travessia de pré-ordem dos valores de seus nós. Faça isso com uma solução recursiva e sem usar recursão.

 class TreeNode(var `val`: Int) { var left: TreeNode? = null var right: TreeNode? = null }

Aqui está uma solução recursiva para o problema:

 fun preorderTraversal(root: TreeNode?): List<Int> { val result = mutableListOf<Int>() if (root == null) return result result.add(root.val) result.addAll(preorderTraversal(root.left)) result.addAll(preorderTraversal(root.right)) return result }

Essa função faz um percurso de pré-ordem da árvore binária e retorna uma lista dos valores dos nós na ordem em que são visitados.

O algoritmo funciona da seguinte maneira:

1. Se o nó raiz for nulo, retorne uma lista vazia.
2. Adicione o valor do nó raiz à lista de resultados.
3. Atravesse recursivamente a subárvore esquerda chamando a função no filho esquerdo da raiz e adicione a lista retornada à lista de resultados.
4. Atravesse recursivamente a subárvore direita chamando a função no filho direito da raiz e adicione a lista retornada à lista de resultados.
5. Retorna a lista de resultados.

Este algoritmo tem uma complexidade de tempo de O(n), onde n é o número de nós na árvore, e uma complexidade de espaço de O(h), onde h é a altura da árvore (devido à pilha de chamadas).

Aqui está uma solução usando uma abordagem iterativa (ou seja, sem usar recursão):

 fun preorderTraversal(root: TreeNode?): List<Int> { val result = mutableListOf<Int>() val stack = Stack<TreeNode>() var current = root while (current != null || stack.isNotEmpty()) { while (current != null) { result.add(current.val) stack.push(current) current = current.left } current = stack.pop() current = current.right } return result }

Essa função faz um percurso de pré-ordem da árvore binária e retorna uma lista dos valores dos nós na ordem em que são visitados. Ele usa uma pilha para rastrear os nós que ainda precisam ser visitados.

O algoritmo funciona da seguinte maneira:

1. Inicialize uma pilha vazia e defina o nó atual como a raiz da árvore.

2. Enquanto o nó atual não for nulo ou a pilha não estiver vazia:

   1. Enquanto o nó atual não é nulo:

      1. Adicione o valor do nó atual à lista de resultados.
      2. Empurre o nó atual para a pilha.
      3. Defina o nó atual como seu filho esquerdo.

   2. Retire o nó superior da pilha e defina o nó atual como seu filho direito.

3. Retorna a lista de resultados.

Este algoritmo tem uma complexidade de tempo de O(n), onde n é o número de nós na árvore, e uma complexidade de espaço de O(h), onde h é a altura da árvore.

Eu espero que isso ajude! Deixe-me saber se você tem alguma dúvida.