Dado un árbol de búsqueda binario y un nodo en él, encuentre el sucesor en orden de ese nodo en la BST.
// Definition for a binary tree node. public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } |
Solución Java
El nodo no tiene un puntero que apunte a su padre. Esto es diferente de Inorder Successor en BST II.
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) { if(root==null) return null; TreeNode next = null; TreeNode c = root; while(c!=null && c.val!=p.val){ if(c.val > p.val){ next = c; c = c.left; }else{ c= c.right; } } if(c==null) return null; if(c.right==null) return next; c = c.right; while(c.left!=null) c = c.left; return c; } |
Cuando el árbol está equilibrado, la complejidad del tiempo es O (log (n)) y el espacio es O (1). La complejidad de tiempo del peor caso es O (n).
