desarrollobackend.com

{ Desarrollo BACKEN:D }

BLOG

Resolviendo el Problema de Árboles Binarios Flip Equivalentes

En este artículo, vamos a explorar una solución eficiente al problema de árboles binarios flip equivalentes utilizando el lenguaje de programación Java. Este problema, presente en la plataforma LeetCode, nos reta a determinar si dos árboles binarios son equivalentes mediante una serie de flip operations.

Descripción del Problema

Dado el nodo raíz de dos árboles binarios root1 y root2, debemos retornar true si los árboles son flip equivalentes o false en caso contrario. Un árbol es flip equivalente a otro si podemos convertir uno en otro tras realizar un número de operaciones de flip en varios de sus nodos.

 

Ejemplos:

Ejemplo 1:


Input: root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
Output: true
Explicación: Cambiamos los nodos con valores 1, 3, y 5.

Ejemplo 2:

Input: root1 = [], root2 = []
Output: true

Ejemplo 3:

Input: root1 = [], root2 = [1]
Output: false

 

Enfoque para la Solución

Para resolver este problema, debemos utilizar una función recursiva que compare los subárboles de cada nodo, considerando las dos posibilidades: sin flipping y con flipping. Si ambos árboles llegan a tener estructuras equivalentes tras ciertas operaciones de flipping, entonces son equivalentes.

Código Java


public class Solution {
    public boolean flipEquiv(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) return true;
        if (root1 == null || root2 == null || root1.val != root2.val) return false;

        return (flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right)) ||
               (flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left));
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}
 

Conclusión

La solución propuesta es eficiente y se encarga de comparar exhaustivamente todas las posibilidades de flip en los árboles. Conseguimos así resolver el problema de los árboles binarios flip equivalentes en el contexto del desafío de programación de LeetCode.