Advertisement
Guest User

Untitled

a guest
Jan 21st, 2019
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.32 KB | None | 0 0
  1. private Node<E> findLCA(Node<E> root, Node<E> n1, Node<E> n2) {
  2.  
  3.         //Condições de paragem
  4.         if(root == null)
  5.             return null;
  6.  
  7.         if(n1.getElement() == root.getElement() || n2.getElement() == root.getElement())
  8.             return root;
  9.  
  10.         //Obter elemento da esquerda:
  11.         Node<E> left = findLCA(root.left, n1, n2);
  12.  
  13.         //Obter elemento da direita:
  14.         Node<E> right = findLCA(root.right, n1, n2);
  15.  
  16.         //Se ambos metodos retornarem um valor diferente de null, então o LCA é a root.
  17.         if(left != null && right != null)
  18.             return root;
  19.  
  20.         return left != null ? left : right;
  21.     }
  22.  
  23.     /**
  24.      * Descobre a distância entre dois nodes.
  25.      * @param origin
  26.      * @param destination
  27.      * @return
  28.      */
  29.     private int distanceTo(Node<E> origin, Node<E> destination) {
  30.  
  31.         //Verificações:
  32.         if(origin == null || destination == null)
  33.             return 0;
  34.  
  35.         //Calcular comparação:
  36.         int c = destination.getElement().compareTo(origin.getElement());
  37.  
  38.         //Se elementos forem iguais, retornamos 0:
  39.         if(c == 0)
  40.             return 0;
  41.  
  42.         //Caso contrário escolhemos a direção:
  43.         return c < 0 ? 1+distanceTo(origin.left, destination) : 1+distanceTo(origin.right, destination);
  44.  
  45.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement