Problema
Implemente un iterador sobre un árbol de búsqueda binario (BST). Su iterador se inicializará con el nodo raíz de una BST. Llamar a next () devolverá el siguiente número más pequeño en el BST. Nota: next () y hasNext () deben ejecutarse en un tiempo promedio de O (1) y usan la memoria O (h), donde h es la altura del árbol.
Solución Java
La clave para resolver este problema es comprender las características de BST. Aquí hay un ejemplo de BST.
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class BSTIterator { Stack<TreeNode> stack; public BSTIterator(TreeNode root) { stack = new Stack<TreeNode>(); while (root != null) { stack.push(root); root = root.left; } } public boolean hasNext() { return !stack.isEmpty(); } public int next() { TreeNode node = stack.pop(); int result = node.val; if (node.right != null) { node = node.right; while (node != null) { stack.push(node); node = node.left; } } return result; } } |
