[Leetcode] 0951. Árboles binarios equivalentes de inversión

Explore diversas soluciones LeetCode en Python, C++, JavaScript, SQL y TypeScript. Ideal para preparación de entrevistas, aprendizaje y práctica de código en múltiples lenguajes de programación. Enlace de repositorio de Github

Tabla de contenido

Medio

Para un árbol binario T, podemos definir una operación de volteo de la siguiente manera: elija cualquier nodo e intercambie los subárboles secundarios izquierdo y derecho.

Un árbol binario incógnita es equivalente de volteo a un árbol binario Y Si y sólo si podemos hacerlo incógnita igual a Y después de una cierta cantidad de operaciones de inversión.

Dadas las raíces de dos árboles binarios raíz1 y raíz2, devolver verdadero Si los dos árboles son equivalentes inversos o FALSO de lo contrario.

Ejemplo 1:

Aporte: raíz1 = [1,2,3,4,5,6,nulo,nulo,nulo,7,8], raíz2 = [1,3,2,nulo,6,4,5,nulo,nulo,nulo,nulo,8,7]
Producción: verdadero
Explicación: Giramos los nodos con valores 1, 3 y 5.

Ejemplo 2:

Aporte: raíz1 = [], raíz2 = []
Producción: verdadero

Ejemplo 3:

Aporte: raíz1 = [], raíz2 = [1]
Producción: FALSO

Restricciones:

El número de nodos en cada árbol está en el rango [0, 100].
Cada árbol tendrá valores de nodo únicos en el rango [0, 99].

Pitón

				
					Complejidad de tiempo #: O(n) Complejidad de espacio #: O(n) de la importación de tipos Clase opcional TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def traverse(node): si el nodo es None: return si node.val: print(node.val) si node.left: traverse(node.left) si node.right: traverse(node.right) Solución de clase: def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool: si no es root1 y no root2: devuelve True si no es root1 o no root2: devuelve False si root1.val != root2.val: devuelve False return (self.flipEquiv(root1.left, root2.left) y self.flipEquiv(root1.right, root2.right)) o (self.flipEquiv(root1.left, root2.right) y self.flipEquiv(root1.right, root2.left)) root1 = NodoÁrbol(1) root1.left = NodoÁrbol(2) root1.right = NodoÁrbol(3) root1.left.left = NodoÁrbol(4) root1.left.right = NodoÁrbol(5) root1.right.left = NodoÁrbol(6) root1.left.right.left = NodoÁrbol(7) root1.left.right.right = NodoÁrbol(8) root2 = NodoÁrbol(1) root2.left = NodoÁrbol(3) root2.right = NodoÁrbol(2) root2.left.right = NodoÁrbol(6) root2.right.left = NodoÁrbol(4) root2.right.right = NodoÁrbol(5) root2.right.right.left = NodoÁrbol(8) root2.right.right.right = NodoÁrbol(7) imprimir(Solución().flipEquiv(raíz1, raíz2))

Medio

Pitón

Artículos relacionados