Dado un árbol binario, determine si es un árbol de búsqueda binario válido (BST).
Suponga que una BST se define de la siguiente manera:
- El subárbol izquierdo de un nodo contiene solo nodos con claves menores que la clave del nodo.
- El subárbol derecho de un nodo contiene solo nodos con claves mayores que la clave del nodo.
- Tanto los subárboles izquierdo como derecho también deben ser árboles de búsqueda binarios.
Solución Java 1: recursivo
Todos los valores del subárbol izquierdo deben ser menores que el padre y el padre del padre, y todos los valores del subárbol derecho deben ser mayores que el padre y el padre del padre. Entonces solo verificamos los límites de cada nodo.
public boolean isValidBST(TreeNode root) { return isValidBST(root, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY); } public boolean isValidBST(TreeNode p, double min, double max){ if(p==null) return true; if(p.val <= min || p.val >= max) return false; return isValidBST(p.left, min, p.val) && isValidBST(p.right, p.val, max); } |
Esta solución también va primero al subárbol izquierdo. Si la violación ocurre cerca de la raíz pero en el subárbol derecho, el método aún cuesta tiempo O (n) y espacio O (h).
La siguiente solución puede manejar violaciones cercanas al nodo raíz más rápidamente.
public boolean isValidBST(TreeNode root) { return helper(root, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY); } public boolean helper(TreeNode root, double min, double max){ if(root==null){ return true; } if(root.val<=min||root.val>=max){ return false; } boolean isLeftBST = helper(root.left, min, root.val); boolean isRightBST = helper(root.right, root.val, max); if(!isLeftBST||!isRightBST){ return false; } return true; } |
Solución Java 2: iterativa
public class Solution { public boolean isValidBST(TreeNode root) { if(root == null) return true; LinkedList<BNode> queue = new LinkedList<BNode>(); queue.add(new BNode(root, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY)); while(!queue.isEmpty()){ BNode b = queue.poll(); if(b.n.val <= b.left || b.n.val >=b.right){ return false; } if(b.n.left!=null){ queue.offer(new BNode(b.n.left, b.left, b.n.val)); } if(b.n.right!=null){ queue.offer(new BNode(b.n.right, b.n.val, b.right)); } } return true; } } //define a BNode class with TreeNode and it's boundaries class BNode{ TreeNode n; double left; double right; public BNode(TreeNode n, double left, double right){ this.n = n; this.left = left; this.right = right; } } |
El tiempo y el espacio son ambos O (n).
Solución Java 3: recorrido en orden
Dado que el recorrido en orden de BST es ascendente, podemos verificar la secuencia. El tiempo es O (n) y el espacio es O (h). h es la altura de la pila que es la altura del árbol.