Блог

Пример дерева:

                 1
              /    
             2      3
            /     / 
           4   5  6   7
          /        
         8          9
        / 
       10  11
  

Задан случайный узел. Скажем, 6. Как мне найти самый дальний узел от него?

Только учитывая дерево, невозможно обойти изучение всего дерева O (n). Вот простой алгоритм, проходящий по дереву и посещающий каждый узел один раз:

 int maxD;
Node furthest;
Node findFurthest(Node node) {
    maxD = 0;
    furthest = node;
    Node prev = null;
    for (int d = 0; node != null; d  ) {
        explore(node, d, prev);
        prev = node;
        node = node.parent;
    }
    return furthest;
}
void explore(Node node, int d, Node prev) {
    if (node == null)
        return;
    if (d > maxD) {
        maxD = d;
        furthest = node;
    }
    if (node.left != prev)
        explore(node.left, d   1, null);
    if (node.right != prev)
        explore(node.right, d   1, null);
}
  

Если бы вы сохранили максимальную глубину на каждом ребре или на узлах, вы могли бы ответить на запрос в O (logn), перейдя к проверке корня и сравнивая глубины, а затем спустившись к листу с самым дальним расстоянием. Хотя это верно только в том случае, если вам просто нужно вернуть один из самых дальних узлов, а не все из них, если они имеют одинаковое расстояние.