LeetCode Tree Preguntas: Lo que debe saber

Los problemas del árbol de Leetcode son una opción popular para las preguntas de las entrevistas. Los árboles se utilizan en estructuras de archivos, estructuras de organización, evaluación de sintaxis, aprendizaje automático y muchas más aplicaciones. Además, dominar los problemas de árboles es un buen paso antes de aprender a resolver problemas de gráficos. En esta publicación de blog, compartiré lo que aprendí al resolver 100 preguntas de árbol en leetcode.

Tipos de árboles

Un árbol es una estructura jerárquica con un conjunto de nodos conectados. Cada nodo se puede conectar a muchos hijos , pero debe estar conectado exactamente a un padre. Aquí hay un ejemplo de un árbol:

Decimos que un nodo es una hoja si no tiene hijos. Las hojas en el diagrama anterior son 50, 5, 22, 16, 4 y 3.

Un árbol binario es un árbol en el que cada nodo tiene como máximo dos hijos, el hijo izquierdo y el hijo derecho. El árbol anterior no es un árbol binario, ya que los nodos 10 y 11 tienen más de 2 hijos. Por el contrario, este es un árbol binario:

Un árbol de búsqueda binaria es un árbol binario donde cada nodo satisface la propiedad del árbol de búsqueda binaria. Para un nodo dado, todos los nodos del subárbol izquierdo son más pequeños que este nodo y todos los nodos del subárbol derecho son mayores que este nodo. Aquí hay un ejemplo de un árbol de búsqueda binaria:

Recorridos de árboles

Hay diferentes algoritmos para atravesar árboles. Cada recorrido tiene diferentes aplicaciones que pueden adaptarse a un tipo de problema en particular.

Un recorrido en orden es específico de los árboles binarios. Atraviesa el subárbol izquierdo, seguido por el nodo raíz, seguido por el subárbol derecho. El nombre inorder se usa porque cuando este recorrido se usa en un árbol de búsqueda binaria, el resultado es una lista ordenada.

Recorrido en orden del BST anterior: 1, 3, 4, 6, 7, 8, 10, 13, 14

Un recorrido en orden previo atraviesa el nodo raíz seguido de los subárboles. En el contexto de un árbol binario, un recorrido de preorden es raíz, izquierda, derecha.

Recorrido de pedido anticipado del BST anterior: 8, 3, 1, 6, 4, 7, 10, 14, 13.

Un recorrido posterior al orden atraviesa los subárboles y luego atraviesa el nodo raíz. En el contexto de un árbol binario, un recorrido posterior al orden es izquierda, derecha, raíz. ¿Cuál sería el recorrido posterior al pedido del BST anterior? Comenta abajo.

Definición del árbol binario de Leetcode

Diferentes preguntas de leetcode definen diferentes interfaces para estructuras de datos y cómo trabajar con ellas. Para preguntas sobre árboles, la definición más común es la definición de árbol binario TreeNode. Leetcode proporciona la siguiente definición de TreeNode:

class TreeNode:
     def __init__(self, val=0, left=None, right=None):
         self.val = val
         self.left = left
         self.right = right

Implementación de recorridos — Suma de rango

Veamos cómo podemos implementar estos recorridos a través de una simple pregunta de LeetCode: Range sum . La pregunta es devolver la suma de todos los valores de todos los nodos en el rango inclusivo [bajo, alto].

Un enfoque simple para resolver esta pregunta es atravesar todos los nodos, para cada nodo verificar si está en el rango y, de ser así, agregar los nodos a una suma. Dado que este es un árbol, debemos usar un recorrido de árbol. Por el bien de esta implementación, dado que solo necesitamos alguna forma de atravesar el árbol, cualquiera de los algoritmos transversales debería funcionar bien.

Usaré el recorrido de preorden. Aquí está el pseudocódigo para el enfoque que implementaré:

1. Caso base: si no hay árbol, devolveré 0 ya que no hay nodos dentro del rango
2. Verificaré si el nodo raíz está dentro del rango, y si es así, agregaré el nodo raíz a la suma
3. Realice una llamada recursiva para llamar a la función en el subárbol izquierdo. Sumar el resultado a la suma.
4. Realice una llamada recursiva para llamar a la función en el subárbol derecho. Sumar el resultado a la suma.
5. devolver la suma

class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        if root is None:
            return 0 
            
        valuesSum = 0 
        if root.val >= low and root.val <= high:
            valuesSum += root.val 
        
        valuesSum += self.rangeSumBST(root.left, low, high)
        valuesSum += self.rangeSumBST(root.right, low, high)
        
        return valuesSum

Nuestra solución anterior funciona. También es un buen ejemplo de cómo implementar transversales. Sin embargo, hemos pasado por alto el hecho de que el árbol es un árbol de búsqueda binaria. Considere un árbol con 1000 nodos, como el siguiente árbol:

El árbol satisface la propiedad Árbol de búsqueda binaria, todos los nodos a la derecha de un nodo determinado son mayores que el nodo. Sin embargo, nuestro algoritmo no aprovecha esta propiedad. Si el rango de valores era [1, 2], el algoritmo aún atraviesa todos los nodos del árbol .

Podemos optimizar el algoritmo utilizando el rango más bajo y más alto para determinar si vale la pena atravesar el rango. Dado que sabemos que todos los nodos a la derecha son mayores que el nodo actual, no necesitamos atravesar a la derecha si el valor actual es mayor que el más alto. Del mismo modo, no es necesario atravesar a la izquierda si el nodo ya es más pequeño que el más bajo. Aquí está el nuevo código para mejorar la eficiencia:

class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        if root is None:
            return 0 
            
        valuesSum = 0 
        if root.val >= low and root.val <= high:
            valuesSum += root.val 
        
        if root.val > low:
            valuesSum += self.rangeSumBST(root.left, low, high)
        if root.val < high:
            valuesSum += self.rangeSumBST(root.right, low, high)
        
        return valuesSum

Travesía de orden de nivel

Finalmente, hay un recorrido más importante en los árboles conocido como recorrido de orden de nivel. El recorrido por orden de nivel es una forma de recorrer un árbol por niveles, nivel por nivel.

Tomemos de nuevo nuestro ejemplo de árbol de búsqueda binaria:

El recorrido del orden de niveles de este árbol es 8, 3, 10, 1, 6, 14, 4, 7, 13.

A diferencia de los otros recorridos, el recorrido por orden de nivel generalmente se implementa de forma iterativa mediante una cola . La cola rastrea todos los nodos actuales que aún no se han atravesado. La idea es sacar un nodo a la vez de la cola y luego agregar los hijos de este nodo a la cola. Recomiendo aprender el recorrido por orden de niveles después de haber practicado algunas preguntas con los otros patrones de recorrido.

Al igual que con cualquier tema de leetcode, una vez que aprendió un tema, es importante practicar. Aquí hay 6 preguntas de leetcode que ahora podrías resolver.

1. La raíz es igual a la suma de los niños
2. Implementar el recorrido posterior al pedido
3. Implementar transversal de pedido anticipado
4. mismo árbol
5. Validar árbol de búsqueda binaria
6. Recorrido de orden de nivel de árbol binario