[Leetcode] 0098. Validar el árbol de búsqueda binaria

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

Dado que raíz de un árbol binario, determinar si es un árbol de búsqueda binaria (BST) válido.

A BST válido se define de la siguiente manera:

El subárbol izquierdo de un nodo contiene solo nodos con claves menos que la clave del nodo.
El subárbol derecho de un nodo contiene solo nodos con claves más que la clave del nodo.
Los subárboles izquierdo y derecho también deben ser árboles de búsqueda binarios.

Ejemplo 1:

Aporte: raíz = [2,1,3]
Producción: verdadero

Ejemplo 2:

Aporte: raíz = [5,1,4,nulo,nulo,3,6]
Producción: FALSO
Explicación: El valor del nodo raíz es 5, pero el valor de su hijo derecho es 4.

Restricciones:

El número de nodos en el árbol está en el rango [1, 10 ⁴ ].
-2 ³¹ <= Nodo.val <= 2 ³¹ - 1

Tabla de contenido

Pitón

				
					# complejidad temporal: O(n) # complejidad espacial: O(n) importar math de writing importar Clase opcional TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right clase Solución: def isValidBST(self, root: Optional[TreeNode]) -> bool: def dfs(node: Optional[TreeNode], low=-math.inf, high=math.inf): si el nodo es None: devuelve True si el nodo.val <= low: devuelve False si el nodo.val >= high: devuelve False devuelve dfs(node.left, low, node.val) y dfs(node.right, node.val, high) devuelve dfs(root) clase Solución: def isValidBST(self, root: Optional[TreeNode]) -> bool: prev = [-math.inf] def dfs(nodo: Opcional[NodoÁrbol], prev): si no nodo: devuelve Verdadero si no dfs(nodo.izquierdo, prev): devuelve Falso si nodo.val <= prev[0]: devuelve Falso prev[0] = nodo.val devuelve dfs(nodo.derecho, prev) devuelve dfs(raíz, prev) raíz1 = NodoÁrbol(2) raíz1.izquierdo = NodoÁrbol(1) raíz1.derecho = NodoÁrbol(3) print(Solución().isValidBST(raíz1)) raíz2 = NodoÁrbol(5) raíz2.izquierdo = NodoÁrbol(1) raíz2.derecho = NodoÁrbol(4) raíz2.derecho.izquierdo = NodoÁrbol(3) raíz2.derecho.derecho = NodoÁrbol(6) print(Solución().isValidBST(raíz2))

Pitón

Artículos relacionados