Найти расстояние между двумя узлами в бинарном дереве

Question

Многие ответы на сети для «нахождения наименьшего общего предка в двоичном дереве» и его дополнительный вопрос «найти расстояние между 2 узлами» имеют 4 вопроса:

1. не считает дублирует
2. не учитывать, если входной узел является недействительным/отсутствует/не в дереве
3. использования хранения экстры/AUX
4. не усечение обхода хотя ответ получен.

Я закодировал этот образец, чтобы преодолеть все недостатки. но поскольку я не нашел «одного» ответа в этом направлении, я был бы признателен, если у моего кода есть существенный недостаток, которого я не вижу. Может быть, нет. Дополнительные глазные яблоки оценили.

public int distance(int n1, int n2) {   
     LCAData lcaData = new LCAData(null, 0, 0); 

     int distance = foundDistance (root, lcaData, n1, n2, new HashSet<Integer>()); 

     if (lcaData.lca != null) { 
      return distance; 
     } else { 
      throw new IllegalArgumentException("The tree does not contain either one or more of input data. "); 
     } 
    } 

    private static class LCAData { 
     TreeNode lca; 
     int count; 

     public LCAData(TreeNode parent, int count) { 
      this.lca = parent; 
      this.count = count; 

     } 
    } 

private int foundDistance (TreeNode node, LCAData lcaData, int n1, int n2, Set<Integer> set) { 
     assert set != null; 

     if (node == null) { 
      return 0; 
     } 

     // when both were found 
     if (lcaData.count == 2) { 
      return 0; 
     } 

     // when only one of them is found 
     if ((node.item == n1 || node.item == n2) && lcaData.count == 1) { 
      // second element to be found is not a duplicate node of the tree. 
      if (!set.contains(node.item)) { 
       lcaData.count++; 
       return 1; 
      } 
     } 

     int foundInCurrent = 0; 
     // when nothing was found (count == 0), or a duplicate tree node was found (count == 1) 
     if (node.item == n1 || node.item == n2) { 
      if (!set.contains(node.item)) { 
       set.add(node.item); 
       lcaData.count++; 
      } 
      // replace the old found node with new found node, in case of duplicate. this makes distance the shortest. 
      foundInCurrent = 1; 
     } 

     int foundInLeft = foundDistance(node.left, lcaData, n1, n2, set); 
     int foundInRight = foundDistance(node.right, lcaData, n1, n2, set); 

     // second node was child of current, or both nodes were children of current 
     if (((foundInLeft > 0 && foundInRight > 0) || 
       (foundInCurrent == 1 && foundInRight > 0) || 
        (foundInCurrent == 1 && foundInLeft > 0)) && 
         lcaData.lca == null) { 
      // least common ancestor has been obtained 
      lcaData.lca = node; 
      return foundInLeft + foundInRight; 
     } 

     // first node to match is the current node. none of its children are part of second node. 
     if (foundInCurrent == 1) { 
      return foundInCurrent; 
     } 

     // ancestor has been obtained, aka distance has been found. simply return the distance obtained 
     if (lcaData.lca != null) { 
      return foundInLeft + foundInRight; 
     } 

     // one of the children of current node was a possible match. 
     return (foundInLeft + foundInRight) > 0 ? (foundInLeft + foundInRight) + 1 : (foundInLeft + foundInRight); 
    } 

Answer 1

Алгоритм по-видимому, (не вытаскивая его на части полностью) исчерпывающе пройти по всему дереву, пока узел не найден там, где есть один узел находится на левой и один справа. И создание дополнительного набора, как вы идете.

Проблема здесь в том, что ваш алгоритм очень неэффективен. Это может соответствовать вашим требованиям, если эта конкретная операция почти никогда не выполняется. Но, как правило, вы могли бы сделать лучше.