Dos elementos de un árbol de búsqueda binaria (BST) se intercambian por error. Recupera el árbol sin cambiar su estructura.
Solución Java
Inorder traveral devolverá valores en un orden creciente. Entonces, si un elemento es menor que su elemento anterior, el elemento anterior es un nodo intercambiado.
public class Solution { TreeNode first; TreeNode second; TreeNode pre; public void inorder(TreeNode root){ if(root==null) return; inorder(root.left); if(pre==null){ pre=root; }else{ if(root.val<pre.val){ if(first==null){ first=pre; } second=root; } pre=root; } inorder(root.right); } public void recoverTree(TreeNode root) { if(root==null) return; inorder(root); if(second!=null && first !=null){ int val = second.val; second.val = first.val; first.val = val; } } } |
