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 em Kotlin, que tem uma propriedade para o valor do nó e propriedades e 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. TreeNode val left right 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: Se o nó raiz for nulo, retorne uma lista vazia. Adicione o valor do nó raiz à lista de resultados. Atravesse recursivamente a subárvore esquerda chamando a função no filho esquerdo da raiz e adicione a lista retornada à lista de resultados. Atravesse recursivamente a subárvore direita chamando a função no filho direito da raiz e adicione a lista retornada à lista de resultados. 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: Inicialize uma pilha vazia e defina o nó atual como a raiz da árvore. Enquanto o nó atual não for nulo ou a pilha não estiver vazia: Enquanto o nó atual não é nulo: Adicione o valor do nó atual à lista de resultados. Empurre o nó atual para a pilha. Defina o nó atual como seu filho esquerdo. Retire o nó superior da pilha e defina o nó atual como seu filho direito. 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.
